1438. Where Two Schedules Overlap
Two people each give a list of busy intervals, both already sorted and each
list internally non-overlapping. Print every stretch during which BOTH are busy,
one per line. If there is no such stretch, print none.
An intersection exists when the later start is at or before the earlier end, and when it exists it runs from that later start to that earlier end. A stretch of zero length, where the two merely touch, counts.
Two pointers walk both lists once. After comparing a pair, advance whichever interval ENDS first, because that one cannot intersect anything further along the other list.
Constraints - `0 ≤ n, m ≤ 100000` - `0 ≤ start ≤ end ≤ 1000000000` - Each list is sorted and internally non-overlapping.
Input
The first line contains two integers n and m.
The next n lines each contain two integers: one interval from the first list.
The next m lines each contain two integers: one interval from the second list.
Output
Print each overlapping stretch on its own line as two space-separated integers, in increasing order. Print none if there are no overlaps.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.