Coding interview pattern
Sort by start, then sweep to merge, insert, or detect overlaps.
The idea
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
Cost
| 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
Translatable skeleton
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
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
In the interview
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.
interval problems - merge overlapping intervals - meeting rooms pattern
An external resource we recommend. AlgoExpert is not affiliated with us and we earn nothing from this link.
Keep going
Track a contiguous subarray or substring without re-scanning it from scratch.
Walk two indices toward or alongside each other to avoid a nested loop.
Halve the search space each step over any monotonic condition, not just sorted arrays.
Solve overlapping subproblems once, store the results, and build the answer up.
See all coding patterns, the coding questions for your role, and the behavioral round.