Merge Intervals

    DSA · Intermediate

    Definition

    Sort intervals by start, then merge each one into the previous if they overlap.

    Appears in calendar, booking and scheduling problems.

    Diagram

    [1,3] [2,6]→ [1,6][8,10] stays

    Flowchart

    Sort by startPush first intervalIf overlap, extend endElse push new interval

    Example: Merge intervals

    iv = [[1, 3], [8, 10], [2, 6]]
out = []
for s, e in sorted(iv):
    if out and s <= out[-1][1]:
        out[-1][1] = max(out[-1][1], e)
    else:
        out.append([s, e])
print(out)

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

    Complexity

    O(n log n)

    Key points

    • Meeting rooms uses a min-heap of end times
    • Sorting is the key step

    Interview questions

    Minimum meeting rooms?

    Sort by start, keep a heap of end times; heap size at most is the answer.

    More DSA topics

    ArraysLinked ListStackQueue