-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.ts
62 lines (49 loc) · 1.53 KB
/
index.ts
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
import { Heap } from "../deps.ts";
export default function getOrder(tasks: number[][]): number[] {
const tasks_indexed: TaskIndexed[] = tasks.map(
([enqueueTime, processingTime], index) => ({
index,
processingTime,
enqueueTime,
}),
);
tasks_indexed.sort((a, b) => -a.enqueueTime + b.enqueueTime);
//console.log(tasks_indexed)
const ans: number[] = [];
const pq = new Heap<TaskIndexed>((a, b) =>
a.processingTime === b.processingTime
? +a.index - b.index
: +a.processingTime - b.processingTime
);
let time = 0;
while (tasks_indexed.length || pq.size()) {
// console.log(time)
if (pq.isEmpty()) {
time = Math.max(
time,
tasks_indexed[tasks_indexed.length - 1].enqueueTime,
);
}
let last = tasks_indexed[tasks_indexed.length - 1];
while (last && last.enqueueTime <= time) {
tasks_indexed.pop();
pq.insert(last);
last = tasks_indexed[tasks_indexed.length - 1];
}
//console.log("last",last,"time",time,tasks_indexed,pq.toArray())
//}
if (pq.size()) {
// console.log("time",time,pq.toArray())
const { index, processingTime } = pq.top();
pq.pop();
time += processingTime;
ans.push(index);
}
}
return ans;
}
type TaskIndexed = {
index: number;
processingTime: number;
enqueueTime: number;
};