1751. Maximum Number of Events That Can Be Attended II

Tags:

• Hard
• backtrack
• binary search

Link

Backtrack

class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        
        events.sort()

        lens = len(events)

        arr = [events[i][0] for i in range(lens)]

        @cache
        def backtrack(i, c):
            if c == 0:
                return 0
            if i == lens:
                return 0

            res = 0

            idx = bisect.bisect_left(arr, events[i][1] + 1)

            res = max(
                events[i][2] + backtrack(idx, c-1),
                backtrack(i+1, c)
            )

            return res

        return backtrack(0, k)