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:
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:
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:
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.length1 <= k * events.length <= 1061 <= startDayi <= endDayi <= 1091 <= valuei <= 106Problem Overview: You are given events[i] = [start, end, value]. You can attend at most k events, and events cannot overlap. The goal is to choose events that maximize the total value while respecting time conflicts.
Approach 1: Dynamic Programming with Binary Search (O(n log n * k) time, O(nk) space)
This is a classic weighted interval scheduling problem with an additional constraint of attending at most k events. Start by sorting events by start time using sorting. For each event, decide whether to skip it or attend it. If you attend it, you must jump to the next event whose start time is greater than the current event's end time. Use binary search to find that next valid index quickly.
Define dp[i][j] as the maximum value achievable starting from event i with j events remaining. The transition compares skipping the event (dp[i+1][j]) versus taking it (value[i] + dp[nextIndex][j-1]). Binary search reduces the search for the next compatible event from O(n) to O(log n), which keeps the solution scalable for large inputs.
This approach works well because the events become independent once the next valid index is found. The combination of dynamic programming and binary search is the standard optimal solution used in most high-quality editorials.
Approach 2: Greedy with Segment Sweeping (O(n log n) time, O(n) space)
Another strategy processes events in chronological order and maintains the best achievable value so far using a sweep-line style traversal. After sorting events by start time, maintain structures that track completed events and the maximum value achievable before each start time. As the sweep progresses, update candidate results and discard expired intervals.
This method treats the timeline as segments where previously completed events contribute to the best achievable value. Efficient updates typically rely on ordered structures or prefix maximum tracking. While conceptually greedy, it still mirrors the weighted interval scheduling idea but compresses transitions using sorted event boundaries.
The segment sweeping approach is useful when you want a timeline-based perspective rather than explicit state DP. However, it is less commonly expected in interviews compared to the DP formulation.
Recommended for interviews: Dynamic Programming with Binary Search. Interviewers expect candidates to recognize the weighted interval scheduling pattern, sort events, and use binary search to locate the next compatible event. A brute-force exploration demonstrates understanding of the constraints, but the optimized DP solution shows strong algorithmic reasoning.
To tackle the problem efficiently, we can use a variant of the Dynamic Programming approach combined with Binary Search. The idea is to sort events by their end times, which helps in handling overlapping issues. Once sorted, for each event, we compute two scenarios: attending the event and not attending. We also use binary search to identify the last non-overlapping event when including the current one. We arrange these scenarios into a DP table where dp[i][j] represents the maximum value we can obtain by considering the first i events with at most j events attended.
The binary search facilitates a quick lookup of the previous event that can be attended before the current one without overlap. The overall complexity is reduced by leveraging efficient lookup using binary search in a sorted list of events' end times.
We start by sorting the events by their end times. Using a dynamic programming table with dimensions [eventsSize+1][k+1], we track the maximum values possible when attending up to k events. Binary search helps identify the latest non-compatible event to incorporate the new event without overlap.
Time Complexity: O(n * k * log n), where n is the number of events. The log n factor arises from binary searching over sorted events.
Space Complexity: O(n * k) for the DP table.
Another alternative approach is to make use of Greedy reasoning combined with a Sweep-Line technique. By first sorting the events based on both start and end times, we can iterate over the events to select the maximum value events that don't overlap. When we encounter a new potential starting event that fits, we check and decide to attend based on maximizing the cumulative event value without exceeding k events.
The Python solution leverages both greedy choice and a min-heap to keep track of current events such that the events do not overlap. While introducing events from the heap, it tests viability considering the constraints, particularly the start and end days.
Time Complexity: O(n log n) due to sorting and heap operations.
Space Complexity: O(n) for storing events in the heap.
First, we sort the events by their start time in ascending order. Then, we define a function dfs(i, k), which represents the maximum total value achievable by attending at most k events starting from the i-th event. The answer is dfs(0, k).
The calculation process of the function dfs(i, k) is as follows:
If we do not attend the i-th event, the maximum value is dfs(i + 1, k). If we attend the i-th event, we can use binary search to find the first event whose start time is greater than the end time of the i-th event, denoted as j. Then, the maximum value is dfs(j, k - 1) + value[i]. We take the maximum of the two options:
$
dfs(i, k) = max(dfs(i + 1, k), dfs(j, k - 1) + value[i])
Here, j is the index of the first event whose start time is greater than the end time of the i-th event, which can be found using binary search.
Since the calculation of dfs(i, k) involves calls to dfs(i + 1, k) and dfs(j, k - 1), we can use memoization to store the computed values and avoid redundant calculations.
The time complexity is O(n times log n + n times k), and the space complexity is O(n times k), where n$ is the number of events.
We can convert the memoization approach in Solution 1 to dynamic programming.
First, sort the events, this time by end time in ascending order. Then define f[i][j] as the maximum total value by attending at most j events among the first i events. The answer is f[n][k].
For the i-th event, we can choose to attend it or not. If we do not attend, the maximum value is f[i][j]. If we attend, we can use binary search to find the last event whose end time is less than the start time of the i-th event, denoted as h. Then the maximum value is f[h + 1][j - 1] + value[i]. We take the maximum of the two options:
$
f[i + 1][j] = max(f[i][j], f[h + 1][j - 1] + value[i])
Here, h is the last event whose end time is less than the start time of the i-th event, which can be found by binary search.
The time complexity is O(n times log n + n times k), and the space complexity is O(n times k), where n$ is the number of events.
Related problems:
| Approach | Complexity |
|---|---|
| Dynamic Programming with Binary Search | Time Complexity: O(n * k * log n), where n is the number of events. The log n factor arises from binary searching over sorted events. |
| Greedy with Segment Sweeping | Time Complexity: O(n log n) due to sorting and heap operations. |
| Memoization + Binary Search | — |
| Dynamic Programming + Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Binary Search | O(n log n * k) | O(nk) | General case. Best choice for interviews and large inputs. |
| Greedy with Segment Sweeping | O(n log n) | O(n) | Useful when modeling the problem as timeline segments with prefix maximum tracking. |
Maximum Number of Events That Can Be Attended II | Recur | Memo | Leetcode 1751 | codestorywithMIK • codestorywithMIK • 13,097 views views
Watch 9 more video solutions →Practice Maximum Number of Events That Can Be Attended II with our built-in code editor and test cases.
Practice on FleetCode