I don’t get why we have such complexity, don’t we have N^2 here?
// go through all the intervals to find each interval's next interval
for (i = 0; i < n; i++) {
// let's find the next interval of the interval which has the highest 'end'
const [topEnd, endIndex] = maxEndHeap.pop();
result[endIndex] = -1; // defaults to -1
if (maxStartHeap.peek()[0] >= topEnd) {
let [topStart, startIndex] = maxStartHeap.pop();
// find the the interval that has the closest 'start'
while (maxStartHeap.length > 0 && maxStartHeap.peek()[0] >= topEnd) {
[topStart, startIndex] = maxStartHeap.pop();
}
result[endIndex] = startIndex;
// put the interval back as it could be the next interval of other intervals
maxStartHeap.push([topStart, startIndex]);
}
}