https://leetcode.com/problems/find-right-interval

findRightInterval.js

/*
IDEA: If we have a sorted list of starts and ends,
then scanning from left to right, every time we
see a start, that must be the closest interval to
the right of all the ends we've seen so far.

O(nlogn) // nlogn for sorting, + n for a single scan.
*/
var findRightInterval = function(intervals) {
    // 1. Break intervals into start and end events
    const events = [];
    intervals.forEach(([start, end], i) => {
        events.push([true, start, i]); // [isStart, pos, index]
        events.push([false, end, i]);
    });
    // 2. Sort them in order of pos. If there's a tie, ends come before starts
    events.sort((a, b) => {
        if(a[1] !== b[1]) return a[1] - b[1]; // asc order of pos
        return a[0] ? 1 : -1; // if pos is eq, ends come first
    });
    
    const result = new Array(intervals.length).fill(-1); // default to -1
    const ended = new Set(); // track all ended intervals that don't have a matching start

    events.forEach(([isStart, pos, i]) => {
        if(!isStart) return ended.add(i); // if we find an end, add it to the set
        for(let endedIntervalIndex of ended){ // and if we find a start
            ended.delete(endedIntervalIndex); // use it to flush out the ends
            result[endedIntervalIndex] = i; // from the set with i as the answer
        }
    });
    
    return result;
};