Coding interview pattern
Merge Intervals
Sort by start, then sweep to merge, insert, or detect overlaps.
The idea
How the merge intervals pattern works
Interval problems revolve around ranges with a start and an end, and almost all of them are unlocked by the same first move: sort the intervals by start time. Once sorted, a single linear sweep can merge overlapping ranges, insert a new range, count overlaps, or find gaps, because any interval that overlaps the current one must come immediately after it in sorted order. That sort-then-sweep shape is the core of the pattern.
To merge, walk the sorted list keeping a current interval; if the next interval starts at or before the current end, extend the current end to the max of the two ends, otherwise emit the current interval and start a new one. The same skeleton, with a different comparison, handles inserting an interval into a sorted set or detecting whether any two intervals overlap (a meeting-rooms feasibility check).
When the question is how many intervals overlap at once (minimum meeting rooms, maximum concurrent events) a second technique helps: a min-heap of end times, or a sweep over separated start and end events. Push each meeting's end onto the heap; before scheduling the next meeting, pop any meeting that has already ended. The heap size is the number of rooms in use, and its peak is the answer. Recognising whether a problem wants a merge sweep or a concurrency count is the key decision.
Recognition
When to reach for it
- The input is a list of ranges with start and end values.
- You need to merge, insert, or remove overlapping ranges.
- You count concurrent intervals (meeting rooms, CPU load, bookings).
- You look for gaps or the maximum overlap across ranges.
Cost
Time & space complexity
| Operation | Time | Space |
|---|---|---|
| Sort then merge sweep | O(n log n) | O(n) |
| Insert into sorted intervals | O(n) | O(n) |
| Min meeting rooms (heap of ends) | O(n log n) | O(n) |
Worked example
Walkthrough: Merge overlapping intervals
- 1Sort the intervals by their start value.
- 2Initialise the result with the first interval as the current one.
- 3For each subsequent interval, if its start is at most the current end, extend the current end to the maximum of the two ends.
- 4Otherwise there is a gap, so push the current interval to the result and make this one current.
- 5After the loop, push the final current interval; the result is the merged set.
Translatable skeleton
The shape in pseudocode
Language-agnostic on purpose. Translate it to your language of choice.
sort by start; cur = intervals[0]; for it in rest: if it.start <= cur.end: cur.end = max(cur.end, it.end); else: emit(cur); cur = it; emit(cur)Practice
Curated problem set
Work these in order, easy to hard. Each is chosen to drill a different facet of the pattern.
| Problem | Level | Why it fits |
|---|---|---|
| Merge Intervals | Medium | The canonical sort-and-sweep merge. |
| Insert Interval | Medium | Merge a new interval into a sorted set. |
| Non-overlapping Intervals | Medium | Greedy removal (overlaps with the greedy pattern). |
| Meeting Rooms | Easy | Any overlap means infeasible. |
| Meeting Rooms II | Medium | Min rooms via a heap of end times. |
| Interval List Intersections | Medium | Two-pointer over two sorted interval lists. |
Avoid these
Common pitfalls
- Sorting by end when the merge sweep needs sorting by start.
- Using strict less-than where touching intervals (equal endpoints) should merge.
- Forgetting to emit the final accumulated interval after the loop.
- Confusing a merge problem with a concurrency-count problem.
In the interview
How to communicate it live
Recognising the pattern is half the score; saying the right things out loud is the other half. These are the sentences that earn the signal.
Announce the universal first move, sort by start time, and explain that once sorted any overlapping interval must come immediately after the current one, which is what makes the single sweep correct.
Distinguish the two sub-types out loud, a merge sweep versus a concurrency count, because they need different tools, a running current interval for merging and a min-heap of end times for counting rooms.
Clarify whether touching intervals that share an endpoint should merge; the strict-versus-non-strict comparison is a frequent off-by-one and stating your assumption avoids it.
Also searched as
interval problems - merge overlapping intervals - meeting rooms pattern
Last reviewed by the site editor: June 2026
An external resource we recommend. AlgoExpert is not affiliated with us and we earn nothing from this link.
Sources
- Greedy Algorithms I: interval partitioning (lecture slides for Kleinberg and Tardos, Algorithm Design) Kevin Wayne, Princeton University
- Competitive Programmer's Handbook: sweep line algorithms (Chapter 30) Antti Laaksonen, CSES
- Klee's measure problem (union of intervals) Wikipedia
Keep going
Related patterns
These techniques share moves with this one, so the practice carries over.
- Sliding Window
Track a contiguous subarray or substring without re-scanning it from scratch.
- Two Pointers
Walk two indices toward or alongside each other to avoid a nested loop.
- Binary Search
Halve the search space each step over any monotonic condition, not just sorted arrays.
- Dynamic Programming
Solve overlapping subproblems once, store the results, and build the answer up.
Round out your prep
See all coding patterns, the coding questions for your role, and the behavioral round.