Merge two sorted interval lists

You get two lists. Each list is already sorted by start and has no overlaps inside it. Return one sorted list with no overlaps, where any intervals that overlap (or touch) across the two lists become one interval.

Brute force. Concatenate the lists, sort by start, and run the classic Merge Intervals sweep. It is correct and short, and a good thing to say first. But it costs O((m + n) log(m + n)) and ignores the fact that both inputs are already sorted.

Optimal: two pointers + one running interval. This is the merge step of merge sort, fused with the Merge Intervals sweep.

• Keep pointers i into a and j into b.
• At each step, take whichever of a[i] and b[j] has the smaller start. This produces the intervals of both lists in global start order, without sorting.
• Feed each taken interval into the sweep:
  • If the output is empty, or the interval starts after the last output interval ends, append a copy of it.
  • Otherwise it overlaps the last output interval, so extend that interval's end to max(last_end, end).
• When one list runs out, keep feeding the rest of the other list through the same sweep. Do not just copy the tail: its first interval can still overlap the last merged interval.

Why it works. The sweep for Merge Intervals is correct for any sequence sorted by start. The two-pointer step produces exactly that sequence in linear time. Each interval is looked at once.

Touching intervals. Treat intervals as closed: [1, 3] and [3, 5] merge into [1, 5]. Confirm this with the interviewer; for half-open intervals, change <= to < in the overlap test.

Invariants.

• The output is sorted by start, and every pair of neighbors has prev.end < next.start.
• Every interval taken so far is covered by the output, and the output covers nothing else.
• The last output interval is the only one that a future interval can still extend.

from typing import List

Interval = List[int]


def merge_two_interval_lists(a: List[Interval], b: List[Interval]) -> List[Interval]:
    """Merge two sorted, internally non-overlapping interval lists.

    Intervals are closed, so [1, 3] and [3, 5] merge into [1, 5].
    Returns new lists; the inputs are not modified.
    """
    result: List[Interval] = []

    def add(interval: Interval) -> None:
        start, end = interval
        if start > end:
            raise ValueError(f"bad interval {interval}")
        if not result or result[-1][1] < start:
            result.append([start, end])
        else:
            result[-1][1] = max(result[-1][1], end)

    i = j = 0
    while i < len(a) and j < len(b):
        if a[i][0] <= b[j][0]:
            add(a[i])
            i += 1
        else:
            add(b[j])
            j += 1
    while i < len(a):
        add(a[i])
        i += 1
    while j < len(b):
        add(b[j])
        j += 1
    return result


def merge_k_interval_lists(lists: List[List[Interval]]) -> List[Interval]:
    """Follow-up: k sorted lists, using a heap keyed on start."""
    import heapq

    result: List[Interval] = []
    heap = [(lst[0][0], k, 0) for k, lst in enumerate(lists) if lst]
    heapq.heapify(heap)
    while heap:
        _, k, idx = heapq.heappop(heap)
        start, end = lists[k][idx]
        if not result or result[-1][1] < start:
            result.append([start, end])
        else:
            result[-1][1] = max(result[-1][1], end)
        if idx + 1 < len(lists[k]):
            heapq.heappush(heap, (lists[k][idx + 1][0], k, idx + 1))
    return result


if __name__ == "__main__":
    assert merge_two_interval_lists([[1, 4], [8, 10]], [[2, 5], [9, 12], [20, 21]]) == [
        [1, 5], [8, 12], [20, 21]
    ]
    assert merge_two_interval_lists([], []) == []
    assert merge_two_interval_lists([[1, 2]], []) == [[1, 2]]
    assert merge_two_interval_lists([[1, 3]], [[3, 5]]) == [[1, 5]]
    assert merge_two_interval_lists([[1, 2], [6, 7]], [[3, 4]]) == [[1, 2], [3, 4], [6, 7]]
    assert merge_two_interval_lists([[0, 100]], [[1, 2], [5, 6], [99, 150]]) == [[0, 150]]
    assert merge_two_interval_lists([[1, 3], [4, 6], [7, 9]], [[2, 8]]) == [[1, 9]]
    assert merge_two_interval_lists([[5, 5]], [[5, 5]]) == [[5, 5]]
    assert merge_k_interval_lists([[[1, 2]], [[2, 4]], [[10, 11]], []]) == [[1, 4], [10, 11]]
    print("ok")

• Time: O(m + n). Each interval is taken once and the sweep does O(1) work for it. The k-list follow-up is O(N log k) for N total intervals.
• Space: O(1) extra beyond the output (O(m + n) in the worst case, when nothing merges). The k-list version adds O(k) for the heap.

• a = [[1,4],[8,10]], b = [[2,5],[9,12],[20,21]] -> [[1,5],[8,12],[20,21]]
• Both empty: [], [] -> []
• One empty: [[1,2]], [] -> [[1,2]]
• Touching ends: [[1,3]], [[3,5]] -> [[1,5]] (closed intervals)
• No overlaps, interleaved: [[1,2],[6,7]], [[3,4]] -> [[1,2],[3,4],[6,7]]
• One big interval swallows many: [[0,100]], [[1,2],[5,6],[99,150]] -> [[0,150]]
• One interval bridges several from the other list: [[1,3],[4,6],[7,9]], [[2,8]] -> [[1,9]]
• Point intervals, duplicated: [[5,5]], [[5,5]] -> [[5,5]]
• Tail of the longer list overlaps the last merged interval: [[1,10]], [[2,3],[9,12]] -> [[1,12]]

1. Intersection instead of union (LeetCode 986). Same two pointers. The overlap of a[i] and b[j] is [max(starts), min(ends)] when that is non-empty. Then advance the pointer whose interval ends first.
2. k sorted lists. Replace the two-way choice with a min-heap of (start, list_id, index), as in merge_k_interval_lists. O(N log k). Pairwise divide-and-conquer merging also gives O(N log k).
3. Streams or iterators too large for memory. Write it as a generator over two iterators that holds only the current head of each and the pending merged interval. Emit the pending interval as soon as the next start is greater than its end. Memory is O(1).
4. Inputs that are not sorted, or overlap within a list. The sweep still handles overlaps within a list, because it only needs global start order. If the lists are unsorted, sort first (back to O(N log N)), or validate and raise.
5. Free time / gaps. Two people's busy calendars: merge them, then return the gaps between consecutive merged intervals inside a working window. Same merge plus one extra pass.

Mid-level (L4)

• Gives the concatenate-and-sort solution, then improves it to the two-pointer merge without heavy hinting.
• Handles empty lists and the leftover tail correctly, including a tail that still overlaps.
• States O(m + n) time and runs through an example by hand.

Senior (L5)

• Asks about closed vs half-open intervals and whether inputs may be mutated, before coding.
• Writes a single add helper so the main loop and the tail loops share one sweep, with no duplicated merge logic.
• Moves quickly to intersection or k lists and gives the right complexity for each.

Staff (L6+)

• Frames it as "merge of sorted streams + interval sweep" and generalizes to iterators, k-way heaps, and gap finding with no rewrite.
• Discusses input validation and contracts (unsorted input, start > end, very large lists) and what to do at scale, such as streaming or merging sharded calendars.
• Writes tests that target the tricky cases: touching ends, one interval bridging many, and an overlapping tail.