Maximum Number of Events That Can Be Attended II LeetCode solution in Python

1
import bisect
2
from functools import lru_cache
3

4

5
class Solution:
6
    def maxValue(self, events: List[List[int]], k: int) -> int:
7
        if k == 1:  # optimization for TLE test case 57/67
8
            return max([event[2] for event in events])
9

10
        events.sort()
11
        event_starts = [event[0] for event in events]  # enables binary search
12

13
        @lru_cache(None)
14
        def dp(i, j):
15
            if j == 0:  # out of turns
16
                return 0
17
            if i >= len(events):  # end of events array
18
                return 0
19
            max_score = events[i][2]
20

21
            # get minimum index where start day is greater than current end day
22
            next_index_minimum = bisect.bisect_left(event_starts, events[i][1] + 1)
23

24
            # check each possibility from the minimum next index until end of the array
25
            for k in range(next_index_minimum, len(events)):
26
                max_score = max(max_score, events[i][2] + dp(k, j - 1))
27

28
            # check if we can get a better score if we skip this index altogether
29
            max_score = max(max_score, dp(i + 1, j))
30
            return max_score
31

32
        return dp(0, k)