hardDynamic Programming 2DPure DSA~50 min
Maximum Value Attending at Most K Events
Each event has a fixed day range and a value. You can attend at most k events, never two that overlap on any day. Maximize total value attended.
Problem
Given events where events[i] = [start, end, value] (inclusive days) and an integer k, attend at most k non-overlapping events to maximize the sum of their values. Two events overlap if they share any day, including touching endpoints. Return the maximum value.
Input
An array events of [start, end, value] and an integer k.
Output
An integer: the maximum total value of at most k non-overlapping events.
Constraints
- 1 <= k <= events.length <= 10^6 (test sizes here up to a few thousand)
- 1 <= start <= end <= 10^9
- 1 <= value <= 10^6
Examples
Example 1
Input
events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
Output
7
Attend [1,2,4] then [3,4,3] (non-overlapping) for 4 + 3 = 7.
Example 2
Input
events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
Output
9
Pick the three highest non-overlapping single-day events: 4+3+2 = 9.