Merge Intervals
- Apply the sort-then-scan template to merge overlapping intervals in one pass, handling both partial overlap and full containment correctly
- Select the right sort key based on the problem goal: start time for merging, end time for activity selection, event time for sweep-line counting
- Count concurrent intervals using a sweep line with proper tie-breaking for meeting-room and maximum-overlap problems
- Intersect two sorted interval lists using a two-pointer approach that advances past fully-consumed intervals without redundant comparisons
Most interval problems cannot be solved efficiently by checking every pair. The search space is too large and overlapping relationships are scattered across the input. Sorting by start time makes the scan tractable: the algorithm processes intervals left to right and only compares each new interval against the last merged interval, which tracks the farthest end reached by the current overlap group. If an earlier raw interval could have overlapped the current one, its coverage is already absorbed into that last merged interval. One comparison is sufficient. This is what makes a linear scan after sorting correct for five structurally different interval operations: merge, insert, intersect, count concurrency, and select non-overlapping.
Merge Intervals
intervals.sort((a, b) => a[0] - b[0])What Are Interval Problems?
Five distinct operations appear across interval problems. Each one has a different goal, a different sort order, and a different scan invariant:
- Merge: Combine overlapping intervals into one (Merge Intervals)
- Insert: Add a new interval and re-merge (Insert Interval)
- Intersect: Find where two sets of intervals overlap (Interval List Intersection)
- Count: Track how many intervals are active at each point (Meeting Rooms)
- Select: Choose maximum non-overlapping intervals (Non-Overlapping Intervals)
Two intervals overlap when neither ends before the other starts. When intervals are sorted by start time and processed into a merged result, this simplifies to checking whether the current interval's start falls before the end of the last merged interval. That single comparison drives almost every interval algorithm.
Building the Intuition
Attempt 1: Check All Pairs
The brute force approach compares every pair of intervals to find overlaps. For n intervals, that's O(n²) comparisons per pass. But merging two intervals can create new overlaps, so the outer while-loop may restart up to O(n) times, making this O(n³) worst case.
Attempt 2: What If We Sorted?
Consider these unsorted intervals: [[8,10], [1,3], [15,18], [2,6], [9,12]]. The overlapping pairs are scattered: [1,3] overlaps [2,6], and [8,10] overlaps [9,12]. Finding them requires checking every pair.
Now sort by start time: [[1,3], [2,6], [8,10], [9,12], [15,18]]. Suddenly every overlap is between adjacent intervals. No scattered pairs to hunt for. One left-to-right scan finds them all.
The Sort-Then-Scan Template
| Problem | Sort By | Why |
|---|---|---|
| Merge Intervals | Start time | Groups overlapping intervals together |
| Insert Interval | Already sorted | Three contiguous phases emerge |
| Non-Overlapping Intervals | End time | Earliest end leaves most room (activity selection) |
| Meeting Rooms II | Events by time | Counts concurrent meetings by processing start/end events |
Why start time for some problems and end time for others? Merging needs intervals ordered by where they begin, while selection problems need them ordered by where they end (to leave maximum room). Sort by Start vs End covers the full reasoning.
The Three Interval Relationships
Every pair of intervals has exactly one of three relationships. Understanding these is the foundation of all interval problems.
Three Interval Relationships
Every pair of intervals has one of three relationships. Understanding these is the foundation of all interval problems.
The relationship depends on how the start of one interval compares to the end of another.
| Relationship | Condition (sorted by start) | Visual |
|---|---|---|
| Overlap | current[0] < last[1] | Bars share a region |
| Adjacent | current[0] == last[1] | Bars touch at a single point |
| Disjoint | current[0] > last[1] | Gap between bars |
Deriving the Overlap Formula
Instead of memorizing when intervals overlap, derive it from when they don't. Two intervals [a,b] and [c,d] are disjoint when one ends before the other starts:
The full formula a < d AND c < b works for any two intervals regardless of order. But when the intervals are sorted by start time, we know a <= c, so the first condition is automatically satisfied (as long as intervals have positive length). Only the second condition needs checking: current[0] < last[1].
<= (merge adjacent intervals). Meeting Rooms uses < (a meeting ending at t=10 doesn't conflict with one starting at t=10). This single character changes the entire solution. Always clarify which semantics the problem uses.Merge Intervals
Given a collection of intervals, merge all overlapping intervals. This is the pattern's namesake problem.
Why sort by start? Sorting by start time groups overlapping intervals together. If [1,3] and [2,6] overlap, sorting ensures [1,3] comes first, so when we reach [2,6] we see it overlaps with the last merged interval and extend it. Without sorting, [2,6] might appear before [1,3] and we'd miss the merge.
Merge Intervals Walkthrough
Input: [[1,3],[2,6],[8,10],[9,12],[15,18]]. Already sorted by start time.
Step 1 of every merge problem: sort by start. Here, input is already sorted.
Two details matter here:
- Sort by start time so overlapping intervals end up next to each other.
- Use
max(last[1], current[1])to merge. Direct assignment (last[1] = current[1]) fails for contained intervals like [1,10] and [2,5].
max(10, 5) = 10 correctly keeps [1,10]. This is the most common bug in merge implementations.max(last[1], current[1]) and verify it handles containment. The max() call is the difference between correct merging and the most common bug in this problem.Insert Interval
Given a sorted, non-overlapping list of intervals and a new interval, insert it and merge if necessary. The input is already sorted, so no sorting needed. This problem is O(n).
Insert Interval: Three Phases
Insert [4,8] into [[1,2],[3,5],[6,7],[8,10],[12,16]]. Three phases, one pass.
The input is already sorted. The algorithm splits into three contiguous regions.
The algorithm splits into three contiguous phases:
Why min/max in Phase 2? The new interval might start before the current interval (use min to capture the earlier start) and might end after it (use max to capture the later end). Both are needed because the new interval can extend in either direction relative to the intervals it overlaps.
< (intervals[i][1] < new_interval[0]) while Phase 2 uses <= (intervals[i][0] <= new_interval[1]). Swapping these operators breaks the algorithm: you'll either miss a merge or include a non-overlapping interval.Insert Interval runs in O(n) because the input is already sorted. No sorting step needed. A single linear scan walks through three contiguous phases (before, merge, after), touching each interval exactly once.
Interval List Intersection
Given two sorted lists of intervals, find all intersections. This is the two-pointer variation of interval problems.
Interval Intersection: Two Pointers
Two sorted interval lists. Find all intersections using two pointers i and j.
Both lists are sorted by start time. We scan both simultaneously.
The intersection formula: The intersection of [a,b] and [c,d] is [max(a,c), min(b,d)], and it exists only when max(a,c) <= min(b,d). This formula generalizes to rectangle and box intersection in higher dimensions.
Advance the pointer whose interval ends first. That interval can't intersect with anything later in the other list. The other interval might still overlap with the next entry in the first list.
Meeting Rooms: Counting Concurrency
Meeting Rooms II asks: what is the minimum number of conference rooms needed to hold all meetings? This introduces the sweep line technique, which works differently from merge-and-scan.
Meeting Rooms: Sweep Line
Meetings: [0,30], [5,10], [15,20]. How many rooms do we need?
The sweep line approach: decompose into events, sort, scan.
Merging intervals won't work here because it loses overlap count. Merging [0,30] and [5,10] produces [0,30], which looks like one room. But both meetings run simultaneously from time 5 to 10, so you need two rooms. The sweep line tracks when each meeting starts and ends independently, keeping concurrency visible.
The sweep line decomposes each interval into two point events, then scans them in order:
Tie-breaking matters. When a meeting ends and another starts at the same time, the ending event must be processed first. Otherwise you'd count an extra room that isn't needed. The sort key (time, delta) achieves this because -1 < +1.
Alternative: Min-Heap Approach
Sort meetings by start time. Maintain a min-heap of end times, where each entry represents a room and when it becomes free. For each meeting, compare its start time against the heap's minimum (the earliest ending meeting currently in progress). If that earliest meeting ends before this one starts, pop it off the heap. That room is now freed. Then push the new meeting's end time onto the heap. If the earliest meeting hasn't ended yet, the new meeting needs its own room, so just push without popping. The heap size at any point is the number of rooms currently in use.
| Approach | Intuition | When to Use |
|---|---|---|
| Sweep Line | Decompose into events, count with +1/-1 | When you only need the count (simpler code) |
| Min-Heap | Track actual room state with end times | When you need to know which room each meeting uses |
Non-Overlapping Intervals
Given a collection of intervals, find the minimum number of intervals to remove so that the rest are non-overlapping. This is activity selection in disguise: maximizing kept = minimizing removed.
Non-Overlapping Intervals: Sort by End
Intervals: [[1,2],[2,3],[3,4],[1,3]]. Find minimum removals for no overlaps.
This is activity selection in disguise: maximize kept = minimize removed.
Why sort by end, not start? This is the same exchange argument from activity selection. An interval that ends earlier is compatible with everything a later-ending one is compatible with, plus potentially more. Sorting by start time can greedily keep an interval that blocks multiple future ones.
Concrete Failure of Sort-by-Start
Sorting by start greedily picked [1,10] because it started earliest. But [1,10] is a "bully" interval that blocks three smaller ones. Sorting by end avoids this: [1,10] ends last, so it's considered last and correctly rejected.
Advanced Variations
Remove Covered Intervals
An interval [a,b] is covered by [c,d] if c <= a and b <= d. Given a list of intervals, return the number of remaining intervals after removing all covered ones.
The key insight is the sort order: sort by start ASC, and for ties, by end DESC. This ensures that when two intervals share the same start, the longer one comes first and establishes itself as the "covering" interval.
The invariant: after processing each interval, max_end equals the furthest-reaching end of any non-covered interval seen so far. An interval [start, end] is covered iff end <= max_end. The sort ensures that for any two intervals with the same start, the longer one (larger end) comes first and establishes max_end before the shorter one is checked.
Minimum Number of Arrows to Burst Balloons
Each balloon is an interval on the x-axis. An arrow shot at position x bursts all balloons where start <= x <= end. Find the minimum number of arrows to burst all balloons.
This is activity selection in disguise: min arrows = number of non-overlapping groups. Each arrow handles one group of overlapping balloons. The code is structurally identical to Non-Overlapping Intervals.
Sort by Start vs End: When It Matters
Sorting by start vs end is the most common source of bugs in interval problems. The wrong choice produces code that passes some test cases but fails on others.
| Sort By | Use When | Problems |
|---|---|---|
| Start time | You need to process intervals left-to-right and merge/compare neighbors | Merge Intervals, Meeting Rooms I, Interval Intersection |
| End time | You need to maximize non-overlapping selections (activity selection) | Non-Overlapping Intervals, Min Arrows to Burst Balloons |
| Events (sweep line) | You need to count concurrent intervals at each point in time | Meeting Rooms II, Min Platforms, My Calendar |
Concrete Walkthrough
Consider intervals [[1,10], [2,3], [3,5], [5,7], [8,9]] for the "maximum non-overlapping" problem:
Sort-by-start greedily committed to the long interval [1,10], which blocked everything else. Sort-by-end tries short intervals first, leaving room for more.
current[0] <= last[1]. With sort-by-end, you'd need to check both endpoints.Debugging Interval Problems
Check for empty input
Forgetting this guard causes IndexError when accessing intervals[0].
Single interval returns unchanged
Identical intervals: behavior differs by problem
Contained intervals: use max, not assignment
Touching intervals: clarify the overlap definition
Integer overflow in Java and C++
Python doesn't overflow, but Java and C++ do. When interval endpoints are near Integer.MAX_VALUE, arithmetic on them can wrap around. Compare endpoints directly instead of computing sums or differences.
Mutating the input in-place
Complexity at a Glance
| Problem | Time | Space | Why |
|---|---|---|---|
| Merge Intervals | O(n log n) | O(n) | Sort dominates; output is O(n) merged intervals |
| Insert Interval | O(n) | O(n) | Already sorted; single scan builds output |
| Interval Intersection | O(m+n) | O(m+n) | Two pointers; output can be O(m+n) |
| Meeting Rooms I | O(n log n) | O(1) | Sort + single bool check, no output array |
| Meeting Rooms II | O(n log n) | O(n) | Sort + sweep line or heap |
| Non-Overlapping | O(n log n) | O(1) | Sort + counter, no output array |
| Remove Covered | O(n log n) | O(1) | Sort + counter, no output array |
| Min Arrows | O(n log n) | O(1) | Sort + counter, no output array |
Identifying Interval Problems
Use these signal phrases to recognize interval problems instantly:
| Signal Phrase | Problem | Technique |
|---|---|---|
| "merge overlapping" | Merge Intervals | Sort by start, scan and merge |
| "insert into sorted intervals" | Insert Interval | Three-phase scan (before/merge/after) |
| "minimum rooms" or "minimum platforms" | Meeting Rooms II | Sweep line with +1/-1 events |
| "can attend all meetings" | Meeting Rooms I | Sort by start, check consecutive overlaps |
| "remove minimum to avoid overlaps" | Non-Overlapping Intervals | Sort by end, activity selection |
| "intersection of two lists" | Interval Intersection | Two pointers, advance earlier-ending |
| "minimum arrows" or "minimum points" | Burst Balloons | Sort by end, greedy coverage |
| "remove covered intervals" | Remove Covered | Sort by start ASC, end DESC; track max end |
Practice Problems
Problems are grouped by technique, starting with core problems and progressing to variations.
Core Merge & Insert
| Problem | Difficulty | Approach |
|---|---|---|
| Merge Intervals | Medium | Sort by start, merge with max(ends). Using max() prevents shrinking when a contained interval like [2,5] appears inside [1,10]. |
| Insert Interval | Medium | Three contiguous phases, O(n) without re-sorting |
| Interval List Intersection | Medium | Two pointers, advance the earlier-ending pointer |
Scheduling & Rooms
| Problem | Difficulty | Approach |
|---|---|---|
| Meeting Rooms | Easy | Sort by start, check consecutive overlap |
| Meeting Rooms II | Medium | Sweep line or min-heap for concurrency count. Merging intervals would lose overlap information, which is why sweep line is necessary. |
| Employee Free Time | Hard | Merge all employee schedules, find gaps |
Activity Selection
| Problem | Difficulty | Approach |
|---|---|---|
| Non-Overlapping Intervals | Medium | Sort by end, greedy selection, count removals. Sorting by end ensures each kept interval blocks the fewest future options (activity selection). |
| Minimum Number of Arrows to Burst Balloons | Medium | Sort by end, one arrow per non-overlapping group |
| Remove Covered Intervals | Medium | Sort by start (desc end for ties), count non-covered |
Reference Templates
Five compact shapes. Each covers one interval operation. One context sentence precedes each template to describe when to reach for it.
Use when intervals may overlap and the output should combine connected ranges.
Use when the input is already sorted and non-overlapping, so re-sorting would be wasteful.
Use when two sorted interval lists must be compared without checking every pair.
Use when overlap count matters and merging would destroy the overlap information.
Use when the goal is to keep the maximum compatible set or find the minimum removals.
Pattern Recap
Merging overlapping intervals
Sort by start time so that any interval overlapping the current one is guaranteed to be adjacent. A single comparison against the last merged interval is sufficient. When an overlap is found, extend the end using max rather than direct assignment to handle the containment case where the incoming interval ends before the current merged one does.
Inserting into a sorted list
Because the input is already sorted, intervals partition naturally into three contiguous groups relative to the new interval: those that end before it starts, those that overlap with it, and those that start after it ends. A single linear scan handles all three phases without re-sorting, keeping the algorithm at O(n).
Intersecting two sorted lists
Two pointers advance through the lists together. After each comparison, the interval that ends first is fully consumed: every remaining interval in the other list starts later, so this interval cannot contribute any new intersections. Advancing the pointer on the earlier-ending side is the only safe move.
Counting concurrent intervals
The sweep line decomposes each interval into two point events and processes them in time order. When a meeting ends at the same time another begins, processing the end event first frees a room before counting the new arrival, which reflects the correct physical situation. Without that tie-breaking, the count at a shared boundary will be one higher than the actual number of rooms needed.
Selecting maximum non-overlapping intervals
Sort by end time and greedily keep each interval that does not conflict with the last kept one. The exchange argument proves that an interval ending earlier is compatible with at least as many future intervals as any later-ending alternative. Keeping the earliest-ending compatible interval never makes the final count worse.
Rebuilding the Pattern
When an interval problem feels unclear, start by identifying which of the five operations it needs. Merge asks you to combine overlapping intervals. Insert gives you a pre-sorted list and one new interval. Intersection finds where two sorted lists of intervals share coverage. Counting problems ask how many intervals are active simultaneously. Selection problems ask you to keep as many non-overlapping intervals as possible, or equivalently to remove as few as possible.
Once the operation is clear, the sort order follows from the goal. If the problem involves combining intervals or comparing neighbors, sort by start time. Start-time order guarantees that any interval overlapping the current one is immediately adjacent, which is the property that makes a one-pass scan correct. If the problem involves selecting a maximum compatible subset, sort by end time. End-time order implements the activity selection argument: the interval that ends earliest blocks the fewest future intervals and should always be preferred over any later-ending alternative that is currently compatible.
The sweep line approach for counting concurrency requires a different argument. Instead of sorting intervals, you sort events. Each interval produces two events: a start event adds one to the concurrent count, and an end event subtracts one. When a start and an end share the same timestamp, the tie-breaking rule matters. Processing end events before start events at the same time reflects a room being freed before a new meeting claims it. Without this ordering, the count at a shared boundary will be one higher than the actual number of rooms needed.
The activity selection argument for sort-by-end is worth reconstructing from scratch when it feels uncertain. Suppose you have two intervals that are both currently compatible with the last kept interval, and one ends earlier than the other. Any future interval that is compatible with the later-ending one is also compatible with the earlier-ending one, because the earlier-ending one creates strictly less obstruction. The later-ending one may block future intervals that the earlier-ending one would not. Choosing the earlier-ending interval can never be strictly worse, so it is always safe to prefer it.
Insert Interval is the one operation that does not require sorting because the input is already sorted. The three contiguous phases appear because sorted order means intervals cannot interleave: all intervals that end before the new one are grouped at the front, all intervals that overlap with the new one are grouped in the middle, and all intervals that start after the new one are grouped at the end. A single pointer moving from left to right crosses each boundary exactly once.
Check Your Understanding
Use these questions to check whether you can reason through the pattern without looking at the template.
Take Assessment
15 questions covering merge logic, sweep line, sort-by-start vs end, correctness reasoning, and advanced variations.
Practice this pattern
Apply the guide to complete interview problems with explanations and code.
Learn Intervals in a guided sequence
The Interview Course connects this pattern to its prerequisites, worked lessons, and progressively harder problems.