Почему это работает
- У двух интервалов общий кусок от более позднего начала, lo, до более раннего конца, hi. Если lo > hi, один кончается раньше, чем начинается другой, и общего нет.
- Интервал, который кончается раньше, отработал: все следующие интервалы другого списка начинаются после конца текущего, а он и так дальше этого конца. Поэтому сдвигается он, а второй остаётся.
- Оставшийся может встретить ещё что-то: [8, 12] из B даёт [8, 9] с [5, 9], а потом [11, 12] с [11, 12]. Если сдвигать оба сразу, второй кусок потеряется.
Сложность
Время O(n + m): каждый шаг продвигает один из двух списков. Память O(1), не считая результата.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗