Interval List Intersections in Python

You get two lists of intervals, first and second. Each interval is a pair [start, end]. It covers every point from its start to its end.

Return a list of the overlaps between the two lists, from left to right. An overlap is the part that an interval of first shares with an interval of second.

Each list is sorted by start. Inside one list, no two intervals overlap or touch.

Two intervals that only touch share one point. For example, [1,4] and [4,6] overlap in [4,4].

Example 1:

Input: first = [[2,6],[9,12]], second = [[4,10]]
Output: [[4,6],[9,10]]
Explanation: [4,10] overlaps both intervals of first.
It shares 4 to 6 with [2,6].
It shares 9 to 10 with [9,12].

Example 2:

Input: first = [[0,3],[8,15]], second = [[3,5],[9,10],[12,12]]
Output: [[3,3],[9,10],[12,12]]
Explanation: [0,3] and [3,5] touch at 3.
[9,10] and [12,12] lie inside [8,15].
They overlap it in full.

Example 3:

Input: first = [[1,2],[7,8]], second = [[4,5]]
Output: []
Explanation: [4,5] sits in the gap between [1,2] and [7,8].
No point is in both.

Constraints:

• first holds m intervals, from 0 to 100,000.
• second holds n intervals, from 0 to 100,000.
• Each start and end is a whole number from 0 to 1,000,000,000.
• No start is greater than its end.
• In each list, an interval ends before the next one starts.