Merge intervals

Sort intervals by where they start, and each interval only needs comparing with the one you are building. One pass then merges, inserts or counts them.

3 examples12 to practiceRead · 4 min
The idea

After sorting by start, each interval only meets the one being built

An interval is a stretch with a start and an end: a meeting from 9 to 11, a booking for nights 3 to 6. Two intervals overlap when one starts before the other ends.

In an unsorted pile, any interval could overlap any other: O(n²) pairs to check. Sort them by start, and that changes. Walking the sorted list, the current interval can only overlap the one you are building, because everything earlier ends before it or was already merged into it.

The rule

Sort by start time, then keep one open interval: if the next one starts no later than the open one ends, extend the open one; otherwise close it and open the next. O(n log n) for the sort, O(n) for the pass.

Spotting it

Starts and ends, and the word "overlap"

Merge overlapping meetings, bookings or ranges

Sort by start, extend or close

Insert a new range into a sorted, non-overlapping list

Copy before, merge the overlapping middle, copy after

Where two lists of ranges overlap

Two pointers over both sorted lists

The fewest removals so nothing overlaps; the most rooms in use at once

Intervals plus another pattern (greedy, a heap or counting)

Basic

Merge every overlap

Sort, then look at each interval once. The last interval in the result is the open one.

Extending uses the larger of the two ends, not the new end: an interval that sits entirely inside the open one, such as [2, 4] inside [1, 10], must not shrink it.

Medium

Insert a new interval into a sorted list

When the list is already sorted and has no overlaps, there is nothing to sort. Three phases do the job: copy every interval that ends before the new one starts, swallow every interval that overlaps it, then copy the rest.

One pass, O(n), because the input order was already right.

Hard

Two sorted lists: overlap the fronts, drop the one that ends first

With two lists, each already sorted, the overlap of their two front intervals runs from the later start to the earlier end. Whichever front interval ends first can't overlap anything further in the other list, so drop it and compare again. Two pointers, one pass.

The template

The shape to reuse

  1. 1xs ← sorted(intervals) -- by start
  2. 2merged ← []
  3. 3for each iv in xs
  4. 4 if merged is not empty and iv starts ≤ the last merged end
  5. 5 last merged end ← max(last merged end, iv's end)
  6. 6 else
  7. 7 append iv to merged
Traps

Where interval solutions go wrong

Not sorting first

Comparing with the interval being built only works in start order.

Comparing with the previous input interval

In sorted [1, 10], [2, 3], [4, 5], the interval [4, 5] overlaps [1, 10], two places back. Compare with the merged interval, not with the one just before.

Touching ends

Do [1, 3] and [3, 5] overlap? Meetings that end at 3 and start at 3 usually don't clash; ranges of whole numbers 1–3 and 3–5 share the 3. Read the problem and pick ≤ or < on purpose.

Shrinking a container

Extend with max of the two ends.

Counting overlaps at once

"How many rooms are needed" isn't a merge: it needs the most intervals open at the same moment, which takes sorted starts and ends or a heap.

Check yourself

3 questions

1. Sorted intervals [1, 10], [2, 3], [4, 5]. Why compare [4, 5] with the interval being built and not with [2, 3]?
2. The interval being built is [1, 10] and the next one is [2, 4]. What is it afterward?
3. Why is "how many rooms are needed at once" not a plain merge?
Takeaways

Remember this

  • Sort intervals by start, and each one can only overlap the interval being built.
  • Extend the open interval with the larger end; otherwise close it and open the next: O(n log n) with the sort.
  • Decide on purpose whether touching ends overlap, and use another pattern when the question is how many overlap at once.
Practice

Now solve some yourself

Only this topic 0 of 5 solved

  1. Easy
    Total time poisoned by repeated attacks
    Merge intervals
    LeetCode 495(opens in a new tab)
  2. Medium
    Remove intervals covered by another
    Merge intervals
    LeetCode 1288(opens in a new tab)
  3. Medium
    Remove one range to keep the largest overlap
    Merge intervals
    Codeforces 1029C(opens in a new tab)
  4. Medium
    Accept bookings that don't clash
    Merge intervals
    LeetCode 729(opens in a new tab)
  5. Hard
    Track which ranges are covered
    Merge intervals
    LeetCode 715(opens in a new tab)

Mixed with topics you have practiced 0 unlocked

    7 more once you have practiced Prefix sums, Basic sorting, Heaps & priority queues, Greedy algorithms. Play one of its examples to the end and solve one of its problems to unlock them.

    Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.

    Next

    Binary search on the answer

    Continue