Leetcode 1851 Solution

This article provides solution to leetcode question 1851 (maximum-number-of-events-that-can-be-attended-ii)
Categories:
Tags:
Access this page by simply typing in "lcs 1851" in your browser address bar if you have bunnylol configured.

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

Solution

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

        memo = {}
        def dfs(i, k):
            nonlocal events
            if i == len(events) or k == 0:
                return 0

            key = (i, k)
            if key in memo:
                return memo[key]

            j = i + 1
            while j < len(events) and events[j][0] <= events[i][1]:
                j += 1
            memo[key] = max(dfs(i + 1, k), dfs(j, k - 1) + events[i][2])
            return memo[key]

        return dfs(0, k)