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
| class Solution {
public int maxValue(int[][] events, int k) {
Arrays.sort(events, (a, b) -> a[1] - b[1]);
int n = events.length;
int[][] f = new int[n + 1][k + 1];
for (int i = 0; i < n; ++i) {
int p = search(events, i, events[i][0]);
for (int j = 1; j <= k; ++j) {
f[i + 1][j] = Math.max(f[i][j], f[p + 1][j - 1] + events[i][2]);
}
}
return f[n][k];
}
private int search(int[][] events, int right, int upper) {
int left = -1;
while (left + 1 < right) {
int mid = left + right >> 1;
if (events[mid][1] < upper) left = mid;
else right = mid;
}
return left;
}
}
|
wechat
