Why it works
- Two intervals share the part from the later start, lo, to the earlier end, hi. If lo > hi, one ends before the other starts and they share nothing.
- The interval that ends first is done: every later interval of the other list starts after the current one ends, and that is already past this end. So it moves on, and the other one stays.
- The one that stays can meet more: B’s [8, 12] shares [8, 9] with [5, 9] and then [11, 12] with [11, 12]. Moving both at once would lose the second piece.
Complexity
Time O(n + m): each step moves one of the two lists forward. Memory O(1) besides the result.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗