Сложность: medium
Дан массив интервалов, где intervals[i] = [starti, endi] и каждый starti уникален.
Правый интервал для интервала i - это интервал j, такой что startj >= endi и startj минимален. Обратите внимание, что i может быть равен j.
Верните массив индексов правых интервалов для каждого интервала i. Если правого интервала для интервала i не существует, то поставьте -1 в индекс i.
Пример:
Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.
👨💻 Алгоритм:
1⃣Интуиция за этим подходом такова: если мы будем поддерживать два массива - intervals, который отсортирован по начальным точкам, и endIntervals, который отсортирован по конечным точкам. Когда мы выбираем первый интервал (или, скажем, i-ый интервал) из массива endIntervals, мы можем определить подходящий интервал, удовлетворяющий критериям правого интервала, просматривая интервалы в массиве intervals слева направо, так как массив intervals отсортирован по начальным точкам. Допустим, индекс выбранного элемента из массива intervals окажется j.
2⃣Теперь, когда мы выбираем следующий интервал (скажем, (i+1)-ый интервал) из массива endIntervals, нам не нужно начинать сканирование массива intervals с первого индекса. Вместо этого мы можем начать прямо с индекса j, где мы остановились в последний раз в массиве intervals. Это потому, что конечная точка, соответствующая endIntervals[i+1], больше, чем та, которая соответствует endIntervals[i], и ни один из интервалов из intervals[k], таких что 0 < k < j, не удовлетворяет критериям правого соседа с endIntervals[i], а значит, и с endIntervals[i+1] тоже.
3⃣Если в какой-то момент мы достигнем конца массива, т.е. j = intervals.length, и ни один элемент, удовлетворяющий критериям правого интервала, не будет доступен в массиве intervals, мы ставим -1 в соответствующую запись res. То же самое касается всех оставшихся элементов массива endIntervals, конечные точки которых даже больше, чем у предыдущего интервала. Также мы используем хеш-таблицу hash изначально, чтобы сохранить индексы, соответствующие интервалам, даже после сортировки.
😎 Решение:
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;
}Ставь 👍 и забирай 📚 Базу знаний