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