Код Senior Интервалы обновлено
Пересечение двух списков
Условие
Два списка непересекающихся отсортированных интервалов. Верни их попарные пересечения.
Примеры
intervalIntersection([[0, 2], [5, 10]], [[1, 5], [8, 12]]) // [[1, 2], [5, 5], [8, 10]]
intervalIntersection([[1, 3]], [[5, 7]]) // []
intervalIntersection([], [[1, 2]]) // []
Как подойти
Слияние двух отсортированных списков с вычислением пересечения. Формула max начал / min концов - общая; условие start <= end отсеивает пустые пересечения. Двигаем указатель у того, кто заканчивается раньше: он больше ни с чем не пересечётся.
Подсказки: 2
- Пересечение двух интервалов - максимум начал и минимум концов.
- Двигать надо тот список, чей интервал заканчивается раньше.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.