Problem statement

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

Solution

Let us sort intervals by starts.

The idea is to have dynamic programming with state dp(i, taken), where i is index from what we allowed to take our intervals and taken is number of taken intervals. Then:

  1. if taken > k, it means that we take more than we can, return -inf
  2. if i == len(E), it means that we reached the end: we return 0.
  3. Finally we have two choices: or we take i-th interval, then next interval we can take can be found with binary search: we need to find idex of interval, which >= E[i][i] + 1. Or we can not take it, then we just go to the next index.

Complexity

Time complexity is O(n*k*log(n)), space complexity is O(nk), where n = len(E).

Code

class Solution:
    def maxValue(self, E, k):
        E = sorted(E)
        starts = [e[0] for e in E]
        
        @lru_cache(None)
        def dp(i, taken):
            if taken > k: return -inf
            if i == len(E): return 0
            temp = bisect_left(starts, E[i][1] + 1)
            return max(E[i][2] + dp(temp, taken + 1), dp(i+1, taken))
        
        return dp(0, 0)

It is similar to problem 1235 Maximum Profit in Job Scheduling