Interval List Intersections in C#

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

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

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