05 August 2008
给一个events数组，其中 events[i] = [startDayi, endDayi, valuei] ，表示第 i 个会议在 startDayi 天开始，第 endDayi 天结束，如果你参加这个会议，你能得到价值 valuei 。同时给你一个整数 k 表示你能参加的最多会议数目。
同一时间只能参加一个会议。如果你选择参加某个会议，那么你必须 完整 地参加完这个会议。会议结束日期是包含在会议内的，也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。
请你返回能得到的会议价值 最大和 。
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
class Solution {
// 排序+二分+动态规划
public int maxValue(int[][] events, int k) {
int len = events.length;
Arrays.sort(events, (a, b) -> Integer.compare(a[1], b[1]));
int[] prev = new int[len];
for (int i = 0; i < len; i++) {
prev[i] = binaryFind(events, events[i][0]);
}
int[][] dp = new int[len + 5][k + 5];
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= k; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[prev[i - 1] + 1][j - 1] + events[i - 1][2]);
}
}
return dp[len][k];
}
public int binaryFind(int[][] events, int target) {
int left = 0;
int right = events.length - 1;
while (left <= right) {
int mid = (right - left) / 2 + left;
if (events[mid][1] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}
}