Сложность: medium
Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.
Верните пересечение этих двух списков интервалов.
Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.
Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].
Пример:
Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
👨💻 Алгоритм:
1⃣Инициализация указателей:
Завести два указателя i и j, указывающие на начало firstList и secondList соответственно.
2⃣Поиск пересечений:
Пока оба указателя находятся в пределах своих списков, выполнить следующие действия:
Найти максимальное начало и минимальный конец текущих интервалов.
Если начало меньше или равно концу, добавить пересечение в результат.
Сдвинуть указатель списка, у которого текущий интервал заканчивается раньше.
3⃣Возврат результата:
Вернуть список пересечений.
😎 Решение:
public class Solution {
public int[][] IntervalIntersection(int[][] firstList, int[][] secondList) {
List<int[]> result = new List<int[]>();
int i = 0, j = 0;
while (i < firstList.Length && j < secondList.Length) {
int start = Math.Max(firstList[i][0], secondList[j][0]);
int end = Math.Min(firstList[i][1], secondList[j][1]);
if (start <= end) {
result.Add(new int[]{start, end});
}
if (firstList[i][1] < secondList[j][1]) {
i++;
} else {
j++;
}
}
return result.ToArray();
}
}Ставь 👍 и забирай 📚 Базу знаний