Leetcode 1751. Maximum Number of Events That Can Be Attended II

📅2023-07-15🧐108

This is a typicial Dynamic Programming (DP) problem, just like problem of house robber.

In this question, first we need to sort by the start time, so we could traverse the entire events in a sequence. Then we start to design our Top-down solution. Just like Best Time to Buy or Sell Stock , in each step, we can join or not join. so we just maintan status of current event index and remaining k. And the overlapping problem is dp(i + 1, k) or dp(next, k - 1). Here the next is next start of event, we could use binary search to find it.

Here is top-down solution

from bisect import bisect_right

class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        events.sort(key=lambda x: x[0])
        starts = [x for x, _, _ in events]

        @lru_cache(maxsize=None)
        def dp(i, remain):
            if remain == 0 or i == len(events):
                return 0

            next = bisect_right(starts, events[i][1])

            take = events[i][2] + dp(next, remain - 1)
            skip = dp(i + 1, remain)

            return max(take, skip)

        return dp(0, k)