1751. Maximum Number of Events That Can Be Attended II

https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended-ii/

Python

DP with Binary Search

from functools import cache
from math import inf
from bisect import bisect_right


class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        n = len(events)
        events.sort(key=lambda event: (event[0], event[1], event[2]))

        @cache
        def dp(i, remain):
            if not remain or i >= n:
                return 0
            
            right, value = events[i][1], events[i][2]
            j = bisect_right(events, [right, inf, inf])
            
            return max(
                dp(i+1, remain),
                dp(j, remain-1) + value
            )

        return dp(0, k)