Select at most k non-overlapping events to maximize total value.
You are given a list of events, where each event has a start day, an end day, and a value. You may attend an event on any single day within its inclusive date range, but you cannot attend two events that overlap in time. Your task is to choose at most events so that the sum of their values is as large as possible.
This is a weighted interval scheduling variant with a limit on how many events can be taken.
Input Format
events: an array of events, where each event is represented as[startDay, endDay, value]k: the maximum number of events you may attend
Output Format
- Return the maximum total value obtainable by attending at most
knon-overlapping events.
Constraints
- Each event can be attended on one day only within its start/end range
- No two attended events may overlap
- Attend at most
kevents - Event count may be large enough that brute force is not feasible
Example 1
Input
events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
Output
7
Explanation
Attend the first event on day 1 or 2, and the second event on day 3 or 4. These do not overlap, so the total value is 4 + 3 = 7.
Example 2
Input
events = [[1,2,4],[3,5,6],[6,6,5]], k = 2
Output
11
Explanation
Take the second event for value 6 and the third event for value 5. They do not overlap, giving a total of 11.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.