436. Find Right Interval

[Tcdian]

436. Find Right Interval

给定一组区间，对于每一个区间 i，检查是否存在一个区间 j，它的起始点大于或等于区间 i 的终点，这可以称为 j 在 i 的“右侧”。

对于任何区间，你需要存储的满足条件的区间 j 的最小索引，这意味着区间 j 有最小的起始点可以使其成为“右侧”区间。如果区间 j 不存在，则将区间 i 存储为 -1。最后，你需要输出一个值为存储的区间值的数组。

Note

1. 你可以假设区间的终点总是大于它的起始点。
2. 你可以假定这些区间都不具有相同的起始点。

Example 1

Input: [ [1,2] ]

Output: [-1]

Explanation: There is only one interval in the collection, so it outputs -1.

Example 2

Input: [ [3,4], [2,3], [1,2] ]

Output: [-1, 0, 1]

Explanation: There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.

Example 3

Input: [ [1,4], [2,3], [3,4] ]

Output: [-1, 2, -1]

Explanation: There is no satisfied "right" interval for [1,4] and [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point.

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number[][]} intervals
 * @return {number[]}
 */
var findRightInterval = function(intervals) {
    const result = new Array(intervals.length);
    const sortedIntervals = intervals
        .map((interval, index) => [interval, index])
        .sort(([[a]], [[b]]) => a - b);
    sortedIntervals.forEach(([[start, end], index]) => {
        const minRightInterval = sortedIntervals.find((interval) => {
            return interval[0][0] >= end;
        });
        if (minRightInterval === undefined) {
            result[index] = -1;
        } else {
            result[index] = minRightInterval[1];
        }
    });
    return result;
};

• TypeScript Solution

function findRightInterval(intervals: number[][]): number[] {
    const result: number[] = new Array(intervals.length);
    const sortedIntervals = intervals
        .map((interval, index) => [interval, index] as const)
        .sort(([[a]], [[b]]) => a - b);
    sortedIntervals.forEach(([[start, end], index]) => {
        const minRightInterval = sortedIntervals.find((interval) => {
            return interval[0][0] >= end;
        });
        if (minRightInterval === undefined) {
            result[index] = -1;
        } else {
            result[index] = minRightInterval[1];
        }
    });
    return result;
};