-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.cs
More file actions
47 lines (40 loc) · 1.13 KB
/
Solution.cs
File metadata and controls
47 lines (40 loc) · 1.13 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#if DEBUG
using Microsoft.VisualBasic;
#endif
public class Solution
{
public int MaxValue(int[][] events, int k)
{
Array.Sort(events, (a, b) => a[0] - b[0]);
return DP(events, k, 0);
}
readonly Dictionary<(int, int), int> memo = [];
int DP(int[][] events, int remain, int pos)
{
if (remain == 0 || pos >= events.Length) return 0;
var key = (remain, pos);
if (memo.TryGetValue(key, out int cached)) return cached;
// choose it
// 1. pick it
// 2. find next pos is valid
// 3. plus DP
int low = pos + 1, high = events.Length - 1, next = events.Length;
while (low <= high)
{
int mid = low + (high - low) / 2;
if (events[mid][0] > events[pos][1])
{
next = mid;
high = mid - 1;
}
else
{
low = mid + 1;
}
}
int pick = events[pos][2] + DP(events, remain - 1, next);
// skip it
int skip = DP(events, remain, pos + 1);
return memo[key] = Math.Max(pick, skip);
}
}