Maximum Number of Events That Can Be Attended II
Hard · Intervals · Array · Binary Search · Dynamic Programming · Sorting
Problem
You are given an array events where events[i] = [startDay_i, endDay_i, value_i], and an integer k. Attending an event means being there on every day from its start to its end, inclusive, and earns value_i. You can attend only one event at a time, so two chosen events may not share any day: if one ends on day d, the next can start on day d + 1 at the earliest.
You may attend at most k events. Return the largest total value you can collect.
Examples
Input: events = [[1,3,5],[4,6,4],[2,5,8]], k = 2 Output: 9
Taking [1,3] and [4,6] earns 9, beating the single overlapping event worth 8.
Input: events = [[1,3,5],[3,6,4],[2,5,8]], k = 2 Output: 8
Now [1,3] and [3,6] share day 3, so the best is the single event worth 8.
Input: events = [[1,1,2],[2,2,3],[3,3,4]], k = 2 Output: 7
At most two events are allowed, so pick the two most valuable: 3 + 4.
Constraints
- 1 <= k <= len(events)
- 1 <= k · len(events) <= 10^6
- 1 <= startDay_i <= endDay_i <= 10^9
- 1 <= value_i <= 10^6
Approaches
- Baseline: same DP, next event by linear scan — time O(n² + n·k), space O(n)
Follow-up
Without the limit k this is weighted interval scheduling, and one layer of the table is enough. The use cases fix k = 2, where a suffix maximum replaces the table, and drop k on a road where a ride may start exactly where the last one ended.
Related problems
Start free on Cariara · Coding problems · System design studio
