有一堆event，每個event有開始和結束時間以及value，最多參加k個event問最多獲得多少value，DFS+二分查找下一個可以參與的開始時間最早的event
1 #1751
2 #Runtime: 999 ms (Beats 60%)
3 #Memory: 133.9 MB (Beats 20%)
4
5 class Solution(object):
6 def maxValue(self, events, k):
7 """
8 :type events: List[List[int]]
9 :type k: int
10 :rtype: int
11 """
12 n = len(events)
13 events.sort(key=lambda x: x[0])
14 dp = [[-1] * n for _ in range(k + 1)]
15
16 def DFS(idx, cnt):
17 if cnt == 0 or idx == len(events):
18 return 0
19 if dp[cnt][idx] != -1:
20 return dp[cnt][idx]
21 dp[cnt][idx] = max(DFS(idx + 1, cnt), events[idx][2] + DFS(bsearch(events[idx][1]), cnt - 1))
22 return dp[cnt][idx]
23
24 def bsearch(x):
25 l, r = 0, len(events) - 1
26 while l <= r:
27 mid = (l + r + 1) // 2
28 if events[mid][0] <= x:
29 l = mid + 1
30 else:
31 r = mid - 1
32 return l
33
34 return DFS(0, k)