08.14 大疆笔试 后端开发工程师（研发部）B卷 AC
最大权重的无重叠取数组
这里，不用列表，单纯记录pre应该也是可以，但是感觉代码比较麻烦，就图省事了，
排序后，对于新来的区间 [start, end]，权重 w
dp[end] = Math.max(dp[end_i], dp[start_j] + w)
- end_i 表示小于等于end的最大end
- start_j 表示小于等于start的最大end
例如：
// 排序后 // start end weight [2, 5, 3] [1, 6, 2] [3, 8, 10] [7, 9, 5] [7, 9, 10] // [2, 5, 3] come, create [5, 3, [1]] // list: [5, 3, [1]] // [1, 6, 2] come, create [6, 2, [2]] // choose: [6, 2, [2]] OR [5, 3, [1]] // list: [5, 3, [1]], [6, 3, [1]] // [3, 8, 10] come, create [8, 10, [3]] // choose: [6, 3, [1]] OR [8, 10, [3]] // list: [5, 3, [1]], [6, 3, [1]], [8, 10, [3]] // [7, 9, 5] come, create [9, 5, [4]] // choose: [6, 3, [1]] + [9, 5, [4]] OR [3, 8, [10]] // list: [5, 3, [1]], [6, 3, [1]], [8, 10, [3]], [9, 10, [3]] // [7, 9, 10] come, create [9, 10, [5]] // choose: [6, 3, [1]] + [9, 10, [5]] OR [9, 10, [3]] // list: [5, 3, [1]], [6, 3, [1]], [8, 10, [3]], [9, 13, [1, 5]]
代码
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
class Solution {
/* Write Code Here */
public int[] schedule(int[][] arr) {
int n = arr.length;
// 记录数组对应的下标
Map<int[], Integer> map = new HashMap<>();
for(int i = 0; i < n; i++) {
map.put(arr[i], i);
}
// 根据结束时间排序
Arrays.sort(arr, (a, b) -> a[2]-b[2]);
// 结束时间
ArrayList<EndStatus> list = new ArrayList<>();
for(int i = 0; i < n; i++) {
EndStatus status = new EndStatus();
if(list.isEmpty()) {
status.endTime = arr[i][2];
status.weight = arr[i][0];
status.item = new ArrayList<>();
status.item.add(i);
list.add(status);
} else if(list.get(0).endTime > arr[i][1]) { // 起始时间小于endTime // 寻找小于等于结束时间的最大的endTime，比较value值
int nextIdx = findIdx(arr[i][2], list);
s = list.get(nextIdx);
if(s.endTime == status.endTime) {
if(s.weight < status.weight) {
list.set(nextIdx, status);
}
}else if(s.weight < status.weight) {
list.add(status);
}else{
status.weight = s.weight;
status.item = s.item;
list.add(status);
}
} else { // 起始时间大于等于endTime
// 寻找小于等于起始时间的最大的endTime，计算value值
int preIdx = findIdx(arr[i][1], list);
EndStatus s = list.get(preIdx);
status.endTime = arr[i][2];
status.weight = arr[i][0] + s.weight;
List<Integer> tmp = new ArrayList<>(s.item);
tmp.add(i);
status.item = tmp;
// 寻找小于等于结束时间的最大的endTime，比较value值
int nextIdx = findIdx(arr[i][2], list);
s = list.get(nextIdx);
if(s.endTime == status.endTime) {
if(s.weight < status.weight) {
list.set(nextIdx, status);
}
}else if(s.weight < status.weight) {
list.add(status);
}else{
status.weight = s.weight;
status.item = s.item;
list.add(status);
}
}
}
int weightv = 0;
List<Integer> retList = new ArrayList<>();
for(int i = 0; i < n; i++) {
EndStatus s = list.get(i);
if(s.weight > weightv) {
weightv = s.weight;
retList = s.item;
}
}
int ret[] = new int[retList.size()];
for(int i = 0; i < retList.size(); i++){
ret[i] = map.get(arr[retList.get(i)]);
}
return ret;
}
private int findIdx(int time, ArrayList<EndStatus> list) {
int left = 0, right = list.size()-1;
while(left < right) {
int mid = (left + right+1) / 2;
int tmpTime = list.get(mid).endTime;
if(tmpTime > time) {
right = mid - 1;
}else if (tmpTime == time){
return mid;
} else{
left = mid;
}
}
return left;
}
}
class EndStatus{
int endTime;//结束时间
int weight;//权重
List<Integer> item = new ArrayList<>();//任务下标
}