Merge two sorted interval lists

Implement merge_two_interval_lists(a, b).

Each argument is a list of intervals [start, end] with integer endpoints and start <= end. Each list is sorted by start, and no two intervals in the same list overlap. Intervals from different lists may overlap.

Return a single list of intervals, sorted by start, that covers exactly the same points as the two inputs together, with no two output intervals overlapping. Intervals are closed, so intervals that touch at an endpoint are merged.

Constraints

• 0 <= len(a), len(b) <= 10^5
• Aim for O(len(a) + len(b)) time; do not re-sort the combined input.
• Do not modify the input lists.

Example 1

a = [[1, 4], [8, 10]]
b = [[2, 5], [9, 12], [20, 21]]
-> [[1, 5], [8, 12], [20, 21]]

Example 2

a = [[1, 3], [4, 6], [7, 9]]
b = [[2, 8]]
-> [[1, 9]]

[2, 8] bridges all three intervals of a, so the result is one interval.