Merge Two Lists of Non-Overlapping Intervals

You are given two lists of closed integer intervals, a and b. Each interval is represented as a pair [start, end] with start <= end, and it covers every integer point in the inclusive range [start, end].

Within each list the intervals are already sorted in increasing order of start and are pairwise non-overlapping (no two intervals in the same list share any point). The two lists, however, may overlap with each other arbitrarily.

Merge both lists into a single list of non-overlapping closed intervals that covers exactly the union of all input intervals, sorted by start. Two intervals that overlap or that touch at a shared endpoint must be combined into one. For example, [1, 3] and [3, 5] combine into [1, 5] (they share the endpoint 3), and [1, 4] and [2, 6] combine into [1, 6]. Intervals with a gap between them — such as [1, 2] and [4, 5] — stay separate (the value 3 is not covered, and the endpoints 2 and 4 are not equal).

Examples

Example 1

Input: a = [[1, 3], [6, 9]], b = [[2, 5], [8, 10]]
Output: [[1, 5], [6, 10]]

Explanation: [1, 3] and [2, 5] overlap → [1, 5]. [6, 9] and [8, 10] overlap → [6, 10].

Example 2

Input: a = [[1, 2], [5, 6]], b = [[3, 4]]
Output: [[1, 2], [3, 4], [5, 6]]

Explanation: [1, 2] and [3, 4] neither overlap nor share an endpoint (they leave a gap), so all three intervals stay separate.

Example 3

Input: a = [], b = [[1, 5]]
Output: [[1, 5]]

Constraints

• 0 <= a.length, b.length
• 1 <= a.length + b.length <= 100000
• For every interval, start <= end, and both fit in a signed 32-bit integer.
• Each input list is sorted by start and internally non-overlapping.

Output

Return the merged list of non-overlapping closed intervals, sorted by start.