436. Find Right Interval

public class Solution {
    public int[] FindRightInterval(int[][] intervals) {
        int[][] endIntervals = intervals.ToArray();
        Dictionary<int[], int> hash = new Dictionary<int[], int>();
        for (int i = 0; i < intervals.Length; i++) {
            hash[intervals[i]] = i;
        }
        Array.Sort(intervals, (a, b) => a[0] - b[0]);
        Array.Sort(endIntervals, (a, b) => a[1] - b[1]);
        int j = 0;
        int[] res = new int[intervals.Length];
        for (int i = 0; i < endIntervals.Length; i++) {
            while (j < intervals.Length && intervals[j][0] < endIntervals[i][1]) {
                j++;
            }
            res[hash[endIntervals[i]]] = j == intervals.Length ? -1 : hash[intervals[j]];
        }
        return res;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& FindRightInterval(int[][] intervals) {
        int[][] endIntervals = intervals.ToArray();
        unordered_map<int[], int> hash = new unordered_map<int[], int>();
        for (int i = 0; i < intervals.size(); i++) {
            hash[intervals[i]] = i;
        }
        Array.Sort(intervals, (a, b) => a[0] - b[0]);
        Array.Sort(endIntervals, (a, b) => a[1] - b[1]);
        int j = 0;
        vector<int>& res = new int[intervals.size()];
        for (int i = 0; i < endIntervals.size(); i++) {
            while (j < intervals.size() && intervals[j][0] < endIntervals[i][1]) {
                j++;
            }
            res[hash[endIntervals[i]]] = j == intervals.size() ? -1 : hash[intervals[j]];
        }
        return res;
    }
}

public class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int[][] endIntervals = Arrays.copyOf(intervals, intervals.length);
        HashMap<int[], Integer> hash = new HashMap<>();
        for (int i = 0; i < intervals.length; i++) {
            hash.put(intervals[i], i);
        }
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        Arrays.sort(endIntervals, (a, b) -> a[1] - b[1]);
        int j = 0;
        int[] res = new int[intervals.length];
        for (int i = 0; i < endIntervals.length; i++) {
            while (j < intervals.length && intervals[j][0] < endIntervals[i][1]) {
                j++;
            }
            res[hash.get(endIntervals[i])] = j == intervals.length ? -1 : hash.get(intervals[j]);
        }
        return res;
    }
}

var findRightInterval = function(intervals) {
    let endIntervals = intervals.slice();
    let hash = new Map();
    for (let i = 0; i < intervals.length; i++) {
        hash.set(intervals[i], i);
    }
    intervals.sort((a, b) => a[0] - b[0]);
    endIntervals.sort((a, b) => a[1] - b[1]);
    let j = 0;
    let res = new Array(intervals.length).fill(0);
    for (let i = 0; i < endIntervals.length; i++) {
        while (j < intervals.length && intervals[j][0] < endIntervals[i][1]) {
            j++;
        }
        res[hash.get(endIntervals[i])] = j == intervals.length ? -1 : hash.get(intervals[j]);
    }
    return res;
}

class Solution:
    def findRightInterval(self, intervals):
        endIntervals = intervals[:]
        hash = {tuple(interval): i for i, interval in enumerate(intervals)}
        intervals.sort(key=lambda x: x[0])
        endIntervals.sort(key=lambda x: x[1])
        j = 0
        res = [-1] * len(intervals)
        for i in range(len(endIntervals)):
            while j < len(intervals) and intervals[j][0] < endIntervals[i][1]:
                j += 1
            res[hash[tuple(endIntervals[i])]] = -1 if j == len(intervals) else hash[tuple(intervals[j])]
        return res

func findRightInterval(intervals [][]int) []int {
    endIntervals := make([][]int, len(intervals))
    copy(endIntervals, intervals)
    hash := make(map[[2]int]int)
    for i, interval := range intervals {
        hash[[2]int{interval[0], interval[1]}] = i
    }
    sort.Slice(intervals, func(a, b int) bool { return intervals[a][0] < intervals[b][0] })
    sort.Slice(endIntervals, func(a, b int) bool { return endIntervals[a][1] < endIntervals[b][1] })
    j := 0
    res := make([]int, len(intervals))
    for i := 0; i < len(endIntervals); i++ {
        for j < len(intervals) && intervals[j][0] < endIntervals[i][1] {
            j++
        }
        if j == len(intervals) {
            res[hash[[2]int{endIntervals[i][0], endIntervals[i][1]}]] = -1
        } else {
            res[hash[[2]int{endIntervals[i][0], endIntervals[i][1]}]] = hash[[2]int{intervals[j][0], intervals[j][1]}]
        }
    }
    return res
}

Algorithm

Интуиция за этим подходом такова: если мы будем поддерживать два массива - intervals, который отсортирован по начальным точкам, и endIntervals, который отсортирован по конечным точкам. Когда мы выбираем первый интервал (или, скажем, i-ый интервал) из массива endIntervals, мы можем определить подходящий интервал, удовлетворяющий критериям правого интервала, просматривая интервалы в массиве intervals слева направо, так как массив intervals отсортирован по начальным точкам. Допустим, индекс выбранного элемента из массива intervals окажется j.

Теперь, когда мы выбираем следующий интервал (скажем, (i+1)-ый интервал) из массива endIntervals, нам не нужно начинать сканирование массива intervals с первого индекса. Вместо этого мы можем начать прямо с индекса j, где мы остановились в последний раз в массиве intervals. Это потому, что конечная точка, соответствующая endIntervals[i+1], больше, чем та, которая соответствует endIntervals[i], и ни один из интервалов из intervals[k], таких что 0 < k < j, не удовлетворяет критериям правого соседа с endIntervals[i], а значит, и с endIntervals[i+1] тоже.

Если в какой-то момент мы достигнем конца массива, т.е. j = intervals.length, и ни один элемент, удовлетворяющий критериям правого интервала, не будет доступен в массиве intervals, мы ставим -1 в соответствующую запись res. То же самое касается всех оставшихся элементов массива endIntervals, конечные точки которых даже больше, чем у предыдущего интервала. Также мы используем хеш-таблицу hash изначально, чтобы сохранить индексы, соответствующие интервалам, даже после сортировки.

😎