Watch 10 video solutions for Maximum Number of Events That Can Be Attended II, a hard level problem involving Array, Binary Search, Dynamic Programming. This walkthrough by codestorywithMIK has 13,097 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |