function getOrder(tasks: number[][]): number[] {
let currentTime = 0;
tasks = tasks.map((task, i) => [...task, i]).sort((a,b) => a[0] - b[0]);
const tasksHeap = new TasksHeap([]);
const orderedTasks: number[] = [];
let index = 0;
while(index < tasks.length || tasksHeap.size()) {
if (!tasksHeap.size() && currentTime < tasks[index][0]) {
currentTime = tasks[index][0];
}
while(index < tasks.length && tasks[index][0] <= currentTime) {
tasksHeap.insert(tasks[index]);
index++;
}
const item = tasksHeap.popMin();
currentTime += item[1];
orderedTasks.push(item[2]);
}
return orderedTasks;
};
class TasksHeap {
private readonly data: number[][];
constructor(data: number[][]) {
this.data = data;
}
swap(i: number, j: number) {
const temp = this.data[i];
this.data[i] = this.data[j];
this.data[j] = temp;
}
heapify(i: number) {
const leftNode = 2*i+1;
const rightNode = 2*i+2;
let minimalNode;
if (leftNode <= this.data.length-1 && (this.data[leftNode][1] < this.data[i][1]
|| this.data[leftNode][1] === this.data[i][1] && this.data[leftNode][2] < this.data[i][2])) {
minimalNode = leftNode;
} else {
minimalNode = i;
}
if (rightNode <= this.data.length-1 && (this.data[rightNode][1] < this.data[minimalNode][1]
|| this.data[rightNode][1] === this.data[minimalNode][1] && this.data[rightNode][2] < this.data[minimalNode][2])) {
minimalNode = rightNode;
}
if (minimalNode !== i) {
this.swap(i, minimalNode);
this.heapify(minimalNode);
}
}
heapifyUp(i: number) {
const parentIndex = Math.floor((i-1) / 2);
if (parentIndex >= 0 && (this.data[parentIndex][1] > this.data[i][1]
|| this.data[parentIndex][1] === this.data[i][1] && this.data[parentIndex][2] > this.data[i][2])){
this.swap(parentIndex, i);
this.heapifyUp(parentIndex);
}
}
size(): number {
return this.data.length;
}
popMin(): number[] {
const min = this.data[0];
this.swap(0, this.data.length-1);
this.data.pop();
this.heapify(0);
return min;
}
insert(item: number[]) {
this.data.push(item);
this.heapifyUp(this.data.length-1);
}
getHeap() {
return this.data;
}
}