Interval List Intersections in C++

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

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

Each vector is sorted by start. Inside one vector, 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 vector, an interval ends before the next one starts.