The merge intervals pattern handles problems built on ranges with a start and an end: meeting times, booked rooms, covered segments on a number line. The core idea is to sort the intervals by their start value, then sweep through them once, merging any interval that overlaps the one you are currently building. Sorting turns a messy comparison of every pair into a clean single pass.
When to use it#
Look for this pattern when the input is a list of intervals or ranges and the question asks about overlaps, gaps, merges, or insertions. Signal phrases include “merge overlapping,” “can attend all meetings,” “minimum rooms,” and “free time.” Two intervals overlap when the start of the later one is less than or equal to the end of the earlier one.
Worked example#
Merging all overlapping intervals into a minimal set:
1def merge(intervals):
2 intervals.sort(key=lambda pair: pair[0])
3 merged = [intervals[0]]
4 for start, end in intervals[1:]:
5 last = merged[-1]
6 if start <= last[1]: # overlap, extend the current interval
7 last[1] = max(last[1], end)
8 else: # no overlap, start a new interval
9 merged.append([start, end])
10 return merged
11
12print(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))
13# [[1, 6], [8, 10], [15, 18]]
Because the list is sorted by start, you only ever need to compare a new interval against the last one you kept.
Complexity#
Time is O(n log n), dominated by the sort. The sweep itself is O(n). Space is O(n) for the output, or O(log n) to O(n) for the sort depending on the implementation.
Practice problems#
- Merge Intervals
- Insert Interval
- Non-overlapping Intervals
- Meeting Rooms I and II
- Interval List Intersections
- Employee Free Time
Sorting is the enabling step here, so it helps to be fluent with the sorting deep dive. Return to the pattern hub for related range techniques.