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
| class Solution {
public int[] getOrder(int[][] tasks) {
int[][] taskIndex = new int[tasks.length][3];
for (int i = 0; i < tasks.length; i++) {
taskIndex[i][0] = i;
taskIndex[i][1] = tasks[i][0];
taskIndex[i][2] = tasks[i][1];
}
Arrays.sort(taskIndex, (a, b) -> a[1] != b[1] ? a[1] - b[1] : a[0] - b[0]);
PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[1] != b[1] ? a[1] - b[1] : a[0] - b[0]);
int[] ans = new int[tasks.length];
int ansPtr = 0, taskPtr = 0, currTime = 0;
while (ansPtr < ans.length) {
while (taskPtr < taskIndex.length && taskIndex[taskPtr][1] <= currTime) {
minHeap.offer(new int[] { taskIndex[taskPtr][0], taskIndex[taskPtr][2] });
taskPtr += 1;
}
if (!minHeap.isEmpty()) {
int[] currTask = minHeap.poll();
ans[ansPtr] = currTask[0];
currTime += currTask[1];
ansPtr += 1;
} else {
currTime = taskIndex[taskPtr][1];
}
}
return ans;
}
}
|
我们首先记录每个task的进入queue的顺序. 此时我们要创建一个新的数组来记录task的index, queue time和processing time. 然后我们根据index和enque time给sort一下.
之后我们用currTime来记录当前的时间. 如果有tasks的入queue时间小于当前的时间, 那么入queue. 我们使用的是PQ按照index和processing time来取某个task给CPU去处理.
如果某个时刻没有task入queue, 那么我们需要更新currTime到下一个task入queue的时间.
时间复杂度: O(nlogn)
空间复杂度: O(n)
