leetcode - 1751. Maximum Number of Events That Can Be Attended II-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode - 1751. Maximum Number of Events That Can Be Attended II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Description

You are given an array of events where events[i] = [startDayi, endDayi, valuei]. The ith event starts at startDayi and ends at endDayi, and if you attend this event, you will receive a value of valuei. You are also given an integer k which represents the maximum number of events you can attend.

You can only attend one event at a time. If you choose to attend an event, you must attend the entire event. Note that the end day is inclusive: that is, you cannot attend two events where one of them starts and the other ends on the same day.

Return the maximum sum of values that you can receive by attending events.

Example 1:

leetcode - 1751. Maximum Number of Events That Can Be Attended II,OJ题目记录,leetcode,算法,职场和发展

Input: events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
Output: 7
Explanation: Choose the green events, 0 and 1 (0-indexed) for a total value of 4 + 3 = 7.

Example 2:

leetcode - 1751. Maximum Number of Events That Can Be Attended II,OJ题目记录,leetcode,算法,职场和发展

Input: events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
Output: 10
Explanation: Choose event 2 for a total value of 10.
Notice that you cannot attend any other event as they overlap, and that you do not have to attend k events.

Example 3:

leetcode - 1751. Maximum Number of Events That Can Be Attended II,OJ题目记录,leetcode,算法,职场和发展

Input: events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
Output: 9
Explanation: Although the events do not overlap, you can only attend 3 events. Pick the highest valued three.

Constraints:

1 <= k <= events.length
1 <= k * events.length <= 10^6
1 <= startDayi <= endDayi <= 10^9
1 <= valuei <= 10^6

Solution

Solved after learning from other solutions…

Recursive, for each interval, either choose it or not. For helper function, we pass index as the current chosen index.

Time complexity: $o(n^2)$
Space complxity: $o (n)$

Code

class Solution:
    def __init__(self,) -> None:
        self.memo = {}

    def maxValue(self, events: List[List[int]], k: int) -> int:
        
        def helper(event_index: int, k: int) -> int:
            """
            event_index:
            k:
            """
            if event_index >= len(events) or k == 0:
                return 0
            if (event_index, k) in self.memo:
                return self.memo[(event_index, k)]
            i = event_index + 1
            while i < len(events):
                if events[i][0] > events[event_index][1]:
                    break
                i += 1                
            self.memo[(event_index, k)] = max(helper(i, k - 1) + events[event_index][2], helper(event_index + 1, k))
            return self.memo[(event_index, k)]
        
        events.sort()
        return helper(0, k)

Since events is sorted, we could also use binary search.

class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        events.sort()
        memo = {}
        def helper(index: int, k: int) -> int:
            if index >= len(events) or k == 0:
                return 0
            if (index, k) in memo:
                return memo[(index, k)]
            # find next appropriate index
            left, right = index + 1, len(events) - 1
            while left < right:
                mid = (left + right) >> 1
                if events[mid][0] <= events[index][1]:
                    left = mid + 1
                else:
                    right = mid
            mid = (left + right) >> 1
            if events[mid][0] <= events[index][1]:
                mid += 1
            # keep answer at memo
            ans = max(events[index][2] + helper(mid, k - 1), helper(index + 1, k))
            memo[(index, k)] = ans
            return memo[(index, k)]
        return helper(0, k)

or using bisect package:文章来源地址https://www.toymoban.com/news/detail-593184.html

class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        def helper(index: int, k: int) -> int:
            if k == 0 or index >= len(events):
                return 0
            if (index, k) in memo:
                return memo[(index, k)]
            # looking for next possible index
            i = bisect.bisect_right(events_start, events[index][1])
            res = max(events[index][2] + helper(i, k - 1), helper(index + 1, k))
            memo[(index, k)] = res
            return memo[(index, k)]
        events.sort()
        memo = {}
        events_start = [item[0] for item in events]
        return helper(0, k)