|
|
package class_2022_03_4_week;
|
|
|
|
|
|
import java.util.Arrays;
|
|
|
import java.util.PriorityQueue;
|
|
|
|
|
|
// 来自学员的考试
|
|
|
// 来自华为
|
|
|
// 给定一个n*2的二维数组，表示有n个任务
|
|
|
// 一个信息是任务能够开始做的时间，另一个信息是任务的结束期限，后者一定大于前者，且数值上都是正数
|
|
|
// 你作为单线程的人，不能并行处理任务，但是每个任务都只需要一个单位时间完成
|
|
|
// 你需要将所有任务的执行时间，位于开始做的时间和最后期限之间
|
|
|
// 返回你能否做到这一点
|
|
|
public class Code01_ArrangeJob {
|
|
|
|
|
|
// 1 开 7
|
|
|
// 5 闭 end没有用！
|
|
|
public static class TimePoint {
|
|
|
// 时间
|
|
|
public int time;
|
|
|
public int end;
|
|
|
// add = true time 任务的添加时间
|
|
|
// add = false time 任务的结束时间
|
|
|
public boolean add;
|
|
|
|
|
|
public TimePoint(int t, int e, boolean a) {
|
|
|
time = t;
|
|
|
end = e;
|
|
|
add = a;
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
public static boolean canDo(int[][] jobs) {
|
|
|
if (jobs == null || jobs.length < 2) {
|
|
|
return true;
|
|
|
}
|
|
|
int n = jobs.length;
|
|
|
TimePoint[] arr = new TimePoint[n << 1];
|
|
|
for (int i = 0; i < n; i++) {
|
|
|
arr[i] = new TimePoint(jobs[i][0], jobs[i][1], true);
|
|
|
arr[i + n] = new TimePoint(jobs[i][1], jobs[i][1], false);
|
|
|
}
|
|
|
Arrays.sort(arr, (a, b) -> a.time - b.time);
|
|
|
PriorityQueue<Integer> heap = new PriorityQueue<>();
|
|
|
// 经过一个一个的时间点，遭遇事件：添加时间、检查时间
|
|
|
for (int i = 0, lastTime = arr[0].time; i < arr.length; i++) {
|
|
|
if (arr[i].add) {
|
|
|
heap.add(arr[i].end);
|
|
|
} else { // 检查时间
|
|
|
int curTime = arr[i].time;
|
|
|
for (int j = lastTime; j < curTime; j++) {
|
|
|
if (heap.isEmpty()) {
|
|
|
break;
|
|
|
}
|
|
|
heap.poll();
|
|
|
}
|
|
|
if (heap.peek() <= curTime) {
|
|
|
return false;
|
|
|
}
|
|
|
lastTime = curTime;
|
|
|
}
|
|
|
}
|
|
|
return true;
|
|
|
}
|
|
|
|
|
|
}
|
