Two people each send you their free time as a list of closed intervals [start, end]: both ends are included, so [9, 9] is a single moment. Each list is sorted by start, and the intervals within one list never overlap or touch each other.
Write interval_intersection(first: list[list[int]], second: list[list[int]]) -> list[list[int]] that returns every stretch of time when both are free, as a list of closed intervals sorted by start. A stretch that is a single point counts.
Examples:
interval_intersection([[1, 4], [6, 9], [12, 15]], [[3, 7], [9, 13]])
# [[3, 4], [6, 7], [9, 9], [12, 13]]
[6, 9] meets [3, 7] on [6, 7] and [9, 13] on the single point [9, 9], so one interval can share time with several from the other list.
interval_intersection([[2, 10]], [[1, 3], [5, 6], [8, 12]]) # [[2, 3], [5, 6], [8, 10]]
interval_intersection([[1, 2]], []) # []
Constraints: 0 <= len(first), len(second) <= 10^5, 0 <= start <= end <= 10^9.
⭐ Bonus: a speed test with 40,000 intervals in each list earns a star in O(len(first) + len(second)). Comparing every interval with every other one is O(n · m).
Show hint
look at the two intervals at the front of the lists. Whichever one ends first can't meet anything later in the other list.