Know this before you start: “Merging and overlapping intervals”

Merging and overlapping intervals

Sort intervals by start. Then each one either overlaps the last merged interval (extend it) or starts a new one.

The idea

Two intervals [a, b] and [c, d] overlap when c ≤ b (after sorting by start). Unsorted, an interval could overlap anything; sorted, it can only overlap the most recent merged one.

So one pass is enough: if the next start is ≤ the last end, extend the last end to the max of the two; otherwise begin a new interval.

See it step by step

[[1, 3], [8, 10], [2, 6], [15, 18]]

Sort → [1, 3], [2, 6], [8, 10], [15, 18]
[2, 6] starts at 2 ≤ 3 → merge into [1, 6]
[8, 10] starts after 6 → new. [15, 18] → new. Result [[1, 6], [8, 10], [15, 18]].

In code (Python)

def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)   # a long one can contain later ones
        else:
            merged.append([start, end])
    return merged

print(merge([[1, 3], [8, 10], [2, 6], [15, 18]]))   # [[1, 6], [8, 10], [15, 18]]
print(merge([[1, 10], [2, 3], [4, 5]]))             # [[1, 10]]

O(n log n) for the sort.

When you'll use it

Merge intervals, insert interval, meeting rooms, non-overlapping intervals, calendar bookings.

Common mistakes

Setting the end to the new end instead of the max.
Forgetting to sort first.