Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Unlike maximizing the number of events, maximizing value with an attendance limit needs a take-or-skip decision. After choosing an event, only events starting strictly after its inclusive end remain eligible. Sorting by start time lets binary search find that next state.

Approach

Sort events and extract their start times. Define the best value from event index i with a remaining allowance. Compare skipping to i + 1 against taking the current value plus the state at the first start greater than its end, with one fewer allowed event. Zero remaining allowance or no remaining events contributes zero. Python memoizes this recurrence recursively; JavaScript fills it bottom-up. Return the state beginning at index zero with allowance k.

class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        n = len(events)
        events.sort()
        starts = [s for s, _, _ in events]

        @cache
        def dp(i, count):
            if i == n or count == 0: return 0
            next = bisect_right(starts, events[i][1])
            return max(dp(i + 1, count), dp(next, count - 1) + events[i][2])
        
        return dp(0, k)

Complexity analysis

Let n = events.length. Both solutions use O(n log n + nk log n) time for sorting, up to nk DP states and a binary search per state. Auxiliary space is O(nk + n), including the start array, sorting workspace and DP storage. Python's top-down skip branch can have O(n) recursion depth even when k is small; allowed large event lists can exceed the default recursion limit unless the runner raises it sufficiently. JavaScript fills the table bottom-up without this recursion risk.