-
Notifications
You must be signed in to change notification settings - Fork 41
/
solution.js
86 lines (81 loc) · 1.97 KB
/
solution.js
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/**
* @param {number[][]} tasks
* @return {number[]}
*/
var getOrder = function (tasks) {
tasks.forEach((item, index) => {
item.push(index);
});
tasks.sort((a, b) => {
if (a[0] !== b[0]) {
return a[0] - b[0];
}
if (a[1] !== b[1]) {
return a[1] - b[1];
}
return a[2] - b[2];
});
const heap = [];
const result = [];
heap[0] = tasks[0];
let index = 1;
let endTime = 0;
while (heap.length) {
const node = heap[0];
heap[0] = heap[heap.length - 1];
heap.pop();
sideDonw(heap);
result.push(node[2]);
endTime = Math.max(endTime, node[0]) + node[1];
while (index < tasks.length && tasks[index][0] <= endTime) {
heap.push(tasks[index++]);
sideUp(heap);
}
if (heap.length === 0 && index < tasks.length) {
heap.push(tasks[index++]);
}
}
return result;
};
function sideUp (heap) {
let index = heap.length - 1;
while (index > 0) {
const parent = ((index + 1) >> 1) - 1;
if (isPriority(heap[index], heap[parent])) {
swap(heap, index, parent);
index = parent;
} else {
break;
}
}
}
function sideDonw (heap) {
let index = 0;
while (2 * index + 1 < heap.length) {
let child = 2 * index + 1;
if (child + 1 < heap.length && isPriority(heap[child + 1], heap[child])) {
child++;
}
if (isPriority(heap[child], heap[index])) {
swap(heap, child, index);
index = child;
} else {
break;
}
}
}
function swap (heap, i, j) {
const tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
}
// node1比node2优先吗?
function isPriority (node1, node2) {
if (node1[1] < node2[1]) {
return true;
}
if (node1[1] === node2[1]) {
return node1[2] < node2[2];
}
return false;
}