Compute the Union of Two Sorted Interval Lists

Problem Statement

You are given two lists of closed intervals, listA and listB.

Each list is internally pairwise disjoint and sorted in ascending order by start time. That is, within each list, no two intervals overlap or touch, and listA[i][1] < listA[i+1][0].

Return a single list of closed intervals representing the union of listA and listB. The returned list must also be sorted in ascending order and pairwise disjoint. Note that intervals that touch at an endpoint (e.g., [1, 3] and [3, 5]) should be merged into a single continuous interval (e.g., [1, 5]).

Your solution should run in O(n + m) time, where n and m are the lengths of listA and listB respectively.

Function Signature

def interval_union(listA: list[list[int]], listB: list[list[int]]) -> list[list[int]]:
    pass

Examples

Example 1

Input:
listA = [[1, 3], [6, 9]]
listB = [[2, 5], [10, 12]]

Output:
[[1, 5], [6, 9], [10, 12]]

Explanation:
- [1, 3] and [2, 5] overlap and merge into [1, 5].
- [6, 9] does not overlap with any remaining interval.
- [10, 12] does not overlap with any remaining interval.

Example 2

Input:
listA = [[1, 4], [8, 10]]
listB = [[4, 6], [7, 8]]

Output:
[[1, 6], [7, 10]]

Explanation:
- [1, 4] and [4, 6] touch at endpoint 4 and merge into [1, 6].
- [7, 8] and [8, 10] touch at endpoint 8 and merge into [7, 10].

Constraints

• 0 <= len(listA), len(listB) <= 10^5
• listA[i].length == listB[j].length == 2
• -10^9 <= start_i <= end_i <= 10^9
• Both listA and listB are sorted by start coordinate and contain no overlapping or touching intervals internally.

Edge Cases to Consider

• Either or both lists are empty.
• One list entirely contains an interval from the other list.
• Duplicate identical intervals across both lists.
• Intervals touching at a single boundary point.