Intervals (Merge, Scheduling, Line Sweep)
Table of Contents
Sorting + greedy logic — the framework behind merge, insert, overlap, and scheduling problems that appear in every Google interview loop.
Why Intervals Deserve Their Own Category
An interval is just a pair [start, end] representing a continuous range. But interval
problems form a distinct problem class because they share a common structure that,
once you see it, makes dozens of seemingly different problems collapse into the same few
patterns.
The problems span scheduling (meeting rooms, CPU tasks), geometry (overlapping ranges), data compression (merging ranges), and greedy optimization (maximum non-overlapping set). Yet the underlying techniques are remarkably uniform:
- Sort the intervals (almost always by start time, sometimes by end time).
- Scan left to right, maintaining some state (a merged interval, a pointer, a heap).
- Decide at each step using the relationship between the current interval and your state.
If you master five core patterns, you can solve virtually every interval problem you'll encounter in an interview.
The Three Relationships Between Two Intervals
Every interval problem boils down to understanding how two intervals A = [a1, a2] and
B = [b1, b2] relate to each other. There are exactly three possibilities (assuming
a1 <= b1 after sorting):
Case 1: NO OVERLAP — A ends before B starts
A: ├──────┤
B: ├──────┤
a1 a2 b1 b2
Condition: a2 < b1
Case 2: PARTIAL OVERLAP — they share some range but neither contains the other
A: ├──────────┤
B: ├──────────┤
a1 b1 a2 b2
Condition: a2 >= b1 AND a2 < b2
Overlap region: [b1, a2]
Merged region: [a1, b2]
Case 3: COMPLETE OVERLAP (containment) — one interval contains the other
A: ├────────────────┤
B: ├──────┤
a1 b1 b2 a2
Condition: a2 >= b2
Overlap region: [b1, b2] (all of B)
Merged region: [a1, a2] (all of A)
The critical boundary: Two intervals overlap if and only if a2 >= b1 (assuming
a1 <= b1). This single condition drives nearly every interval algorithm.
Watch for edge cases: When a2 == b1, the intervals share exactly one point. Some
problems treat this as overlapping (merge intervals), others don't (meeting rooms — you
can finish one meeting at time 5 and start another at time 5). Read the problem statement
carefully.
The Foundation: Sort First
Almost every interval problem begins with sorting. But what you sort by depends on the problem:
Sort by Start Time (most common)
Used for: merge intervals, insert interval, interval intersections.
sort(intervals.begin(), intervals.end()); // default: sorts by first element, then second
After sorting by start, intervals are laid out left to right on the number line. You can scan linearly and only look at adjacent/recent intervals to detect overlaps.
Before sorting: [3,6] [1,4] [8,10] [2,5]
After sorting: [1,4] [2,5] [3,6] [8,10]
├──────┤
├──────┤
├──────┤
├────┤
Sort by End Time
Used for: interval scheduling (maximum non-overlapping intervals), minimum arrows.
sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
return a[1] < b[1];
});
Sorting by end time is the classic greedy choice for scheduling. The interval that ends earliest leaves the most room for future intervals.
Sorted by end: [1,2] [1,3] [2,4] [3,5] [4,7]
[1,2] ├──┤ ← ends first, pick this
[1,3] ├─────┤ ← overlaps with [1,2]
[2,4] ├──────┤ ← doesn't overlap with [1,2]? pick!
[3,5] ├──────┤
[4,7] ├──────────┤
Why Sorting Works
Without sorting, detecting overlaps requires comparing every pair: O(n^2). After sorting, you only need to compare adjacent intervals (or maintain a small state), giving O(n) for the scan and O(n log n) overall.
Core Pattern 1 — Merge Overlapping Intervals
Problem: Given a collection of intervals, merge all overlapping intervals.
Template:
Sort by start time.
Initialize merged list with the first interval.
For each subsequent interval:
If it overlaps with the last merged interval → extend the end.
Else → it's a new group, push it.
Visual Walkthrough
Input (after sorting by start):
[1,3] [2,6] [8,10] [15,18]
Step 1: merged = [[1,3]]
Step 2: [2,6] — does it overlap with [1,3]?
start=2 <= end=3 → YES, overlap!
Extend: [1, max(3,6)] = [1,6]
merged = [[1,6]]
Step 3: [8,10] — does it overlap with [1,6]?
start=8 <= end=6? → NO
New group.
merged = [[1,6], [8,10]]
Step 4: [15,18] — does it overlap with [8,10]?
start=15 <= end=10? → NO
New group.
merged = [[1,6], [8,10], [15,18]]
Timeline view:
Before: ├──┤ intervals: [1,3]
├───────┤ [2,6]
├───┤ [8,10]
├────┤ [15,18]
1 2 3 4 5 6 7 8 9 10 15 18
After: ├───────────┤ [1,6]
├───┤ [8,10]
├────┤ [15,18]
Template Code
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged;
for (auto& interval : intervals) {
// If merged is empty OR no overlap with the last merged interval
if (merged.empty() || merged.back()[1] < interval[0]) {
merged.push_back(interval);
} else {
// Overlap — extend the end of the last merged interval
merged.back()[1] = max(merged.back()[1], interval[1]);
}
}
return merged;
}
Why merged.back()[1] < interval[0]? After sorting by start, we only need to check
if the current interval's start is beyond the last merged interval's end. If it is, there's
no overlap. If not, they overlap, and we extend.
Why max(merged.back()[1], interval[1])? Because of containment — the previous
interval might fully contain the current one (e.g., [1,10] and [2,5]), so the merged
end should be the larger of the two.
Complexity: Time O(n log n) for sorting + O(n) scan = O(n log n). Space O(n) for output.
Core Pattern 2 — Insert Into Sorted Intervals
Problem: Given a set of non-overlapping intervals sorted by start, insert a new interval and merge if necessary.
Template:
Three phases:
1. Add all intervals that come entirely BEFORE the new interval.
2. Merge all intervals that OVERLAP with the new interval.
3. Add all intervals that come entirely AFTER the new interval.
Visual Walkthrough
Existing: [1,2] [3,5] [6,7] [8,10] [12,16]
Insert: [4,8]
Phase 1 — Before [4,8]:
[1,2] → end=2 < start=4 → entirely before, add it.
[3,5] → end=5 >= start=4 → STOP, move to phase 2.
Result so far: [[1,2]]
Phase 2 — Overlapping with [4,8]:
[3,5] → start=3 <= end=8 → overlaps! Merge: [min(4,3), max(8,5)] = [3,8]
[6,7] → start=6 <= end=8 → overlaps! Merge: [3, max(8,7)] = [3,8]
[8,10] → start=8 <= end=8 → overlaps! Merge: [3, max(8,10)] = [3,10]
[12,16] → start=12 <= end=10? NO → STOP, move to phase 3.
Result so far: [[1,2], [3,10]]
Phase 3 — After:
[12,16] → add it.
Result: [[1,2], [3,10], [12,16]]
Timeline:
Before: ├┤ ├──┤ ├┤ ├──┤ ├────┤
new: ├────────┤
1 2 3 4 5 6 7 8 9 10 12 16
After: ├┤ ├──────────────┤ ├────┤
1 2 3 10 12 16
Template Code
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int> newInterval) {
vector<vector<int>> result;
int i = 0, n = intervals.size();
// Phase 1: Add all intervals ending before newInterval starts
while (i < n && intervals[i][1] < newInterval[0]) {
result.push_back(intervals[i]);
i++;
}
// Phase 2: Merge all overlapping intervals with newInterval
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = min(newInterval[0], intervals[i][0]);
newInterval[1] = max(newInterval[1], intervals[i][1]);
i++;
}
result.push_back(newInterval);
// Phase 3: Add all remaining intervals
while (i < n) {
result.push_back(intervals[i]);
i++;
}
return result;
}
Complexity: Time O(n) — single pass, no sorting needed (input is already sorted). Space O(n) for output.
Core Pattern 3 — Interval Intersection
Problem: Given two lists of sorted, non-overlapping intervals, find their intersection.
Template:
Two pointers, one for each list.
At each step:
Compute overlap: [max(a_start, b_start), min(a_end, b_end)]
If valid (start <= end) → add to result.
Advance the pointer whose interval ends first.
Why Advance the One That Ends First?
The interval that ends first cannot overlap with anything further in the other list (because the other list is sorted — all future intervals start even later). So we're done with it and move on.
A: [0,2] [5,10] [13,23] [24,25]
B: [1,5] [8,12] [15,24] [25,26]
i=0, j=0: A=[0,2], B=[1,5]
overlap = [max(0,1), min(2,5)] = [1,2] ✓ add [1,2]
A ends at 2, B ends at 5 → advance i (A ends first)
i=1, j=0: A=[5,10], B=[1,5]
overlap = [max(5,1), min(10,5)] = [5,5] ✓ add [5,5]
B ends at 5, A ends at 10 → advance j (B ends first)
i=1, j=1: A=[5,10], B=[8,12]
overlap = [max(5,8), min(10,12)] = [8,10] ✓ add [8,10]
A ends at 10, B ends at 12 → advance i
i=2, j=1: A=[13,23], B=[8,12]
overlap = [max(13,8), min(23,12)] = [13,12] ✗ (13 > 12, invalid)
B ends at 12 → advance j
i=2, j=2: A=[13,23], B=[15,24]
overlap = [max(13,15), min(23,24)] = [15,23] ✓ add [15,23]
A ends at 23 → advance i
i=3, j=2: A=[24,25], B=[15,24]
overlap = [max(24,15), min(25,24)] = [24,24] ✓ add [24,24]
B ends at 24 → advance j
i=3, j=3: A=[24,25], B=[25,26]
overlap = [max(24,25), min(25,26)] = [25,25] ✓ add [25,25]
A ends at 25 → advance i
i=4 → done
Result: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Template Code
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
vector<vector<int>> result;
int i = 0, j = 0;
while (i < A.size() && j < B.size()) {
// Compute the overlap
int lo = max(A[i][0], B[j][0]);
int hi = min(A[i][1], B[j][1]);
if (lo <= hi) {
result.push_back({lo, hi});
}
// Advance the pointer whose interval ends first
if (A[i][1] < B[j][1]) i++;
else j++;
}
return result;
}
Complexity: Time O(m + n) where m and n are the sizes of the two lists. Space O(m + n) for output.
Core Pattern 4 — Minimum Removals for Non-Overlap (Interval Scheduling)
Problem: Given a collection of intervals, find the minimum number of intervals to remove so that the remaining intervals are non-overlapping. Equivalently, find the maximum number of non-overlapping intervals you can keep.
This is the classic Interval Scheduling Maximization Problem from greedy algorithms.
The Greedy Insight: Sort by End Time
Why sort by end time instead of start time?
Consider: [1,10] [2,3] [4,5] [6,7]
Sorted by START: [1,10] [2,3] [4,5] [6,7]
Greedy picks [1,10] first → can only fit 1 interval!
Sorted by END: [2,3] [4,5] [6,7] [1,10]
Greedy picks [2,3] → then [4,5] → then [6,7] → 3 intervals!
The interval that ENDS earliest leaves the most room for future intervals.
This is provably optimal (exchange argument).
The Exchange Argument (Why This Greedy Works)
Claim: The greedy algorithm that always picks the interval with the
earliest end time produces a maximum-size set of non-overlapping intervals.
Proof sketch (exchange argument):
Let G = {g1, g2, ..., gk} be greedy's solution (sorted by end time).
Let O = {o1, o2, ..., om} be any optimal solution (sorted by end time).
We show k >= m.
Key lemma: g_i.end <= o_i.end for all i.
(Greedy's i-th interval ends no later than optimal's i-th interval.)
Proof by induction:
Base: g1 has the earliest end time of all intervals ⇒ g1.end <= o1.end. ✓
Step: Assume g_i.end <= o_i.end.
Then g_{i+1} is chosen from intervals starting after g_i.end.
Since g_i.end <= o_i.end, every interval available to O after o_i
is also available to G after g_i. G picks the one with earliest
end time ⇒ g_{i+1}.end <= o_{i+1}.end. ✓
Since greedy can always continue as long as optimal can: k >= m. ∎
Template Code
#include <bits/stdc++.h>
using namespace std;
// Returns the MINIMUM number of intervals to remove
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) return 0;
// Sort by end time — the greedy choice
sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
return a[1] < b[1];
});
int kept = 1; // keep the first interval
int lastEnd = intervals[0][1]; // track the end of the last kept interval
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] >= lastEnd) { // no overlap (starts at or after lastEnd)
kept++;
lastEnd = intervals[i][1];
}
// else: overlap → skip (remove) this interval
}
return intervals.size() - kept; // removed = total - kept
}
Visual Walkthrough
Input: [[1,2],[2,3],[3,4],[1,3]]
Sorted by end: [[1,2],[2,3],[1,3],[3,4]]
[1,2] ├──┤
[2,3] ├──┤
[1,3] ├─────┤
[3,4] ├──┤
Step 1: Keep [1,2]. lastEnd = 2.
Step 2: [2,3] — start=2 >= lastEnd=2 → Keep. lastEnd = 3.
Step 3: [1,3] — start=1 >= lastEnd=3? NO → Remove.
Step 4: [3,4] — start=3 >= lastEnd=3 → Keep. lastEnd = 4.
Kept: 3 intervals → Remove: 4 - 3 = 1.
Complexity: Time O(n log n). Space O(1) (ignoring sort space).
Core Pattern 5 — Line Sweep (Meeting Rooms)
The line sweep (or event-based) approach treats interval starts and ends as discrete events on a timeline. Instead of working with intervals as pairs, we decompose them into "+1 at start" and "-1 at end" events, then sweep left to right, tracking a running count.
The Idea
Intervals: [0,30] [5,10] [15,20]
Events on timeline:
time 0: +1 (meeting starts)
time 5: +1 (meeting starts)
time 10: -1 (meeting ends)
time 15: +1 (meeting starts)
time 20: -1 (meeting ends)
time 30: -1 (meeting ends)
Sweep left to right, tracking active count:
time 0: count = 1
time 5: count = 2 ← peak! need 2 rooms
time 10: count = 1
time 15: count = 2
time 20: count = 1
time 30: count = 0
Maximum concurrent meetings = 2 → need 2 rooms.
When Lines Just Touch
If a meeting ends at time 10 and another starts at time 10, do they conflict? Usually no — one room suffices. To handle this, process end events before start events at the same time. This is naturally handled if we put ends in one array and starts in another and sort them independently.
Template: Minimum Meeting Rooms (Two-Array Sweep)
#include <bits/stdc++.h>
using namespace std;
int minMeetingRooms(vector<vector<int>>& intervals) {
int n = intervals.size();
vector<int> starts(n), ends(n);
for (int i = 0; i < n; i++) {
starts[i] = intervals[i][0];
ends[i] = intervals[i][1];
}
sort(starts.begin(), starts.end());
sort(ends.begin(), ends.end());
int rooms = 0, maxRooms = 0;
int s = 0, e = 0;
while (s < n) {
if (starts[s] < ends[e]) {
rooms++; // a meeting starts before the earliest one ends
maxRooms = max(maxRooms, rooms);
s++;
} else {
rooms--; // a meeting ends, freeing a room
e++;
}
}
return maxRooms;
}
Alternative: Min-Heap Approach
Instead of decomposing into events, we can use a min-heap to track the end times of all currently active meetings. For each new meeting, if it starts after the earliest-ending active meeting, we reuse that room (pop from heap). Otherwise, we need a new room.
#include <bits/stdc++.h>
using namespace std;
int minMeetingRooms(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end()); // sort by start time
priority_queue<int, vector<int>, greater<int>> minHeap; // end times
for (auto& interval : intervals) {
// If the earliest-ending meeting has ended before this one starts
if (!minHeap.empty() && minHeap.top() <= interval[0]) {
minHeap.pop(); // reuse that room
}
minHeap.push(interval[1]); // assign this meeting a room
}
return minHeap.size(); // heap size = number of rooms in use
}
Why Both Approaches Work
Two-array sweep: Min-heap:
Sorts starts and ends separately. Sorts intervals by start.
Two pointers sweep events. Heap tracks active meeting end times.
O(n log n) time, O(n) space. O(n log n) time, O(n) space.
The two-array sweep is slightly faster in practice (no heap operations), but the min-heap
generalizes better to problems where you need to know WHICH meeting ends (not just when).
Classic Problems with Full Solutions
Problem 1: Merge Intervals (LeetCode 56)
Problem: Given an array of intervals where intervals[i] = [start_i, end_i], merge
all overlapping intervals and return an array of the non-overlapping intervals that cover
all the intervals in the input.
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
[1,3] ├────┤
[2,6] ├────────┤
[8,10] ├───┤
[15,18] ├────┤
1 2 3 4 5 6 7 8 9 10 15 18
Merged:
[1,6] ├───────────┤
[8,10] ├───┤
[15,18] ├────┤
Complete C++ Solution:
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged;
for (auto& interval : intervals) {
if (merged.empty() || merged.back()[1] < interval[0]) {
merged.push_back(interval);
} else {
merged.back()[1] = max(merged.back()[1], interval[1]);
}
}
return merged;
}
int main() {
vector<vector<int>> intervals = {{1,3},{2,6},{8,10},{15,18}};
auto result = merge(intervals);
for (auto& r : result)
cout << "[" << r[0] << "," << r[1] << "] ";
// Output: [1,6] [8,10] [15,18]
}
Complexity: Time O(n log n), Space O(n).
Problem 2: Non-overlapping Intervals (LeetCode 435)
Problem: Given an array of intervals, return the minimum number of intervals you need to remove to make the rest non-overlapping.
Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 1
[1,2] ├──┤
[2,3] ├──┤
[3,4] ├──┤
[1,3] ├─────┤ ← remove this one
Remove [1,3] → remaining [[1,2],[2,3],[3,4]] are non-overlapping.
Key Insight: This is the complement of the Interval Scheduling Maximization problem. Max non-overlapping = greedy with sort-by-end. Removals = total - max non-overlapping.
Complete C++ Solution:
#include <bits/stdc++.h>
using namespace std;
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) return 0;
sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
return a[1] < b[1];
});
int kept = 1;
int lastEnd = intervals[0][1];
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] >= lastEnd) {
kept++;
lastEnd = intervals[i][1];
}
}
return intervals.size() - kept;
}
int main() {
vector<vector<int>> intervals = {{1,2},{2,3},{3,4},{1,3}};
cout << eraseOverlapIntervals(intervals) << "\n"; // Output: 1
}
Why sort by end, not start? Sorting by start and greedily removing the longer interval on conflict also works, but requires more careful handling. Sort by end is cleaner and provably optimal via the exchange argument.
Complexity: Time O(n log n), Space O(1).
Problem 3: Meeting Rooms II (LeetCode 253)
Problem: Given an array of meeting time intervals, find the minimum number of conference rooms required.
Input: [[0,30],[5,10],[15,20]]
Output: 2
Timeline:
Room 1: ├──────────────────────────────────────────────────────┤ [0,30]
Room 2: ├─────────┤ [5,10]
├─────────┤ [15,20]
↑
At time 5, two meetings overlap → need 2 rooms.
Complete C++ Solution (Two-Array Sweep):
#include <bits/stdc++.h>
using namespace std;
int minMeetingRooms(vector<vector<int>>& intervals) {
int n = intervals.size();
vector<int> starts(n), ends(n);
for (int i = 0; i < n; i++) {
starts[i] = intervals[i][0];
ends[i] = intervals[i][1];
}
sort(starts.begin(), starts.end());
sort(ends.begin(), ends.end());
int rooms = 0, maxRooms = 0;
int s = 0, e = 0;
while (s < n) {
if (starts[s] < ends[e]) {
rooms++;
maxRooms = max(maxRooms, rooms);
s++;
} else {
rooms--;
e++;
}
}
return maxRooms;
}
int main() {
vector<vector<int>> intervals = {{0,30},{5,10},{15,20}};
cout << minMeetingRooms(intervals) << "\n"; // Output: 2
}
Step-by-step trace:
starts (sorted): [0, 5, 15]
ends (sorted): [10, 20, 30]
s=0, e=0: starts[0]=0 < ends[0]=10 → rooms=1, maxRooms=1. s=1.
s=1, e=0: starts[1]=5 < ends[0]=10 → rooms=2, maxRooms=2. s=2.
s=2, e=0: starts[2]=15 < ends[0]=10? NO → rooms=1. e=1.
s=2, e=1: starts[2]=15 < ends[1]=20 → rooms=2, maxRooms=2. s=3.
s=3: done.
Answer: maxRooms = 2.
Complexity: Time O(n log n), Space O(n).
Problem 4: Minimum Number of Arrows to Burst Balloons (LeetCode 452)
Problem: Balloons are represented as intervals [x_start, x_end] on a wall. An arrow
shot at position x bursts all balloons where x_start <= x <= x_end. Find the minimum
number of arrows to burst all balloons.
Input: [[10,16],[2,8],[1,6],[7,12]]
Output: 2
[1,6] ├─────────────┤
[2,8] ├──────────────┤
[7,12] ├───────────┤
[10,16] ├───────────┤
1 2 3 4 5 6 7 8 9 10 12 16
Arrow 1 at x=6: bursts [1,6] and [2,8]
Arrow 2 at x=11: bursts [7,12] and [10,16]
Key Insight: This is interval scheduling in disguise. Each "arrow" corresponds to a set of overlapping balloons. Greedily shoot as late as possible within the earliest-ending balloon's range to maximize how many balloons the arrow hits.
Sort by end. Shoot at the end point of the first unbursted balloon. Any balloon whose start is beyond this point needs a new arrow.
Complete C++ Solution:
#include <bits/stdc++.h>
using namespace std;
int findMinArrowShots(vector<vector<int>>& points) {
if (points.empty()) return 0;
// Sort by end position
sort(points.begin(), points.end(), [](auto& a, auto& b) {
return a[1] < b[1];
});
int arrows = 1;
int arrowPos = points[0][1]; // shoot at the end of the first balloon
for (int i = 1; i < points.size(); i++) {
if (points[i][0] > arrowPos) {
// This balloon starts AFTER the arrow position → need new arrow
arrows++;
arrowPos = points[i][1];
}
// else: this balloon is hit by the current arrow (starts before arrowPos)
}
return arrows;
}
int main() {
vector<vector<int>> points = {{10,16},{2,8},{1,6},{7,12}};
cout << findMinArrowShots(points) << "\n"; // Output: 2
}
Step-by-step trace:
Sorted by end: [[1,6],[2,8],[7,12],[10,16]]
Arrow 1 at position 6.
[1,6]: start=1 <= 6 → burst. ✓
[2,8]: start=2 <= 6 → burst. ✓
[7,12]: start=7 > 6 → NOT burst. Need new arrow.
Arrow 2 at position 12.
[7,12]: start=7 <= 12 → burst. ✓
[10,16]: start=10 <= 12 → burst. ✓
Total: 2 arrows.
Note: This is very similar to Non-overlapping Intervals. The key difference:
- Non-overlapping Intervals uses
>=for "no overlap" (start >= lastEnd) because touching endpoints don't overlap. - Burst Balloons uses
>for "needs new arrow" (start > arrowPos) because touching endpoints DO overlap (an arrow at x=6 bursts a balloon at[6,8]).
Complexity: Time O(n log n), Space O(1).
Problem 5: Interval List Intersections (LeetCode 986)
Problem: Given two lists of closed intervals, each list being pairwise disjoint and sorted, return the intersection of these two interval lists.
Input: A = [[0,2],[5,10],[13,23],[24,25]]
B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Timeline:
A: ├──┤ ├─────────┤ ├──────────────────────┤ ├┤
B: ├───────┤ ├───────┤ ├─────────────────┤ ├┤
0 1 2 3 4 5 6 7 8 9 10 13 15 23 24 25 26
∩: ├──┤ ┤ ├──────┤ ├─────────────────┤├┤ ┤
[1,2] [5,5] [8,10] [15, 23] [24,24][25,25]
Complete C++ Solution:
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> intervalIntersection(
vector<vector<int>>& firstList,
vector<vector<int>>& secondList
) {
vector<vector<int>> result;
int i = 0, j = 0;
while (i < firstList.size() && j < secondList.size()) {
int lo = max(firstList[i][0], secondList[j][0]);
int hi = min(firstList[i][1], secondList[j][1]);
if (lo <= hi) {
result.push_back({lo, hi});
}
if (firstList[i][1] < secondList[j][1]) i++;
else j++;
}
return result;
}
int main() {
vector<vector<int>> A = {{0,2},{5,10},{13,23},{24,25}};
vector<vector<int>> B = {{1,5},{8,12},{15,24},{25,26}};
auto result = intervalIntersection(A, B);
for (auto& r : result)
cout << "[" << r[0] << "," << r[1] << "] ";
// Output: [1,2] [5,5] [8,10] [15,23] [24,24] [25,25]
}
Complexity: Time O(m + n), Space O(m + n) for output.
Problem 6: Insert Interval (LeetCode 57)
Problem: Given a set of non-overlapping intervals sorted by start, insert a new interval and merge if necessary. Return the resulting set of non-overlapping intervals.
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Complete C++ Solution:
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int> newInterval) {
vector<vector<int>> result;
int i = 0, n = intervals.size();
// Phase 1: intervals entirely before newInterval
while (i < n && intervals[i][1] < newInterval[0]) {
result.push_back(intervals[i++]);
}
// Phase 2: merge overlapping intervals
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = min(newInterval[0], intervals[i][0]);
newInterval[1] = max(newInterval[1], intervals[i][1]);
i++;
}
result.push_back(newInterval);
// Phase 3: intervals entirely after
while (i < n) {
result.push_back(intervals[i++]);
}
return result;
}
int main() {
vector<vector<int>> intervals = {{1,2},{3,5},{6,7},{8,10},{12,16}};
vector<int> newInterval = {4,8};
auto result = insert(intervals, newInterval);
for (auto& r : result)
cout << "[" << r[0] << "," << r[1] << "] ";
// Output: [1,2] [3,10] [12,16]
}
Step-by-step trace:
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
newInterval = [4,8]
Phase 1 — before [4,8]:
[1,2]: end=2 < 4 → add. result = [[1,2]]
[3,5]: end=5 < 4? NO → stop.
Phase 2 — overlapping with [4,8]:
[3,5]: start=3 <= 8 → merge: [min(4,3), max(8,5)] = [3,8]
[6,7]: start=6 <= 8 → merge: [3, max(8,7)] = [3,8]
[8,10]: start=8 <= 8 → merge: [3, max(8,10)] = [3,10]
[12,16]: start=12 <= 10? NO → stop.
Add [3,10]. result = [[1,2],[3,10]]
Phase 3 — after:
[12,16] → add. result = [[1,2],[3,10],[12,16]]
Complexity: Time O(n), Space O(n).
Problem 7: Meeting Rooms (LeetCode 252)
Problem: Given an array of meeting time intervals, determine if a person could attend all meetings (i.e., no two meetings overlap).
Input: [[0,30],[5,10],[15,20]]
Output: false (meetings [0,30] and [5,10] overlap)
Input: [[7,10],[2,4]]
Output: true (no overlap)
This is the simplest interval problem — just check for ANY overlap.
Complete C++ Solution:
#include <bits/stdc++.h>
using namespace std;
bool canAttendMeetings(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] < intervals[i-1][1]) {
return false; // overlap found
}
}
return true;
}
int main() {
vector<vector<int>> m1 = {{0,30},{5,10},{15,20}};
vector<vector<int>> m2 = {{7,10},{2,4}};
cout << canAttendMeetings(m1) << "\n"; // 0 (false)
cout << canAttendMeetings(m2) << "\n"; // 1 (true)
}
Complexity: Time O(n log n), Space O(1).
When to Use Which Pattern — Decision Framework
Sorting Key Quick Reference
Sort by START time:
• Merge Intervals
• Insert Interval
• Interval Intersection (both lists pre-sorted)
• Meeting Rooms (overlap check)
• Meeting Rooms II (heap approach)
Sort by END time:
• Non-overlapping Intervals (min removals)
• Minimum Arrows to Burst Balloons
• Any "maximum independent set" / interval scheduling problem
Common Mistakes
1. Forgetting to Sort
The number one mistake. Most interval algorithms require sorted input. If the problem says "given a list of intervals," your first line should almost always be a sort.
// WRONG — processing unsorted intervals
for (auto& interval : intervals) { ... }
// RIGHT — sort first
sort(intervals.begin(), intervals.end());
for (auto& interval : intervals) { ... }
2. Sorting by the Wrong Key
"Merge overlapping" → sort by START
"Maximum non-overlapping" → sort by END
Mixing these up gives wrong answers. The reason:
- Merging needs intervals laid out left-to-right (sort by start).
- Scheduling needs the "ends earliest" greedy (sort by end).
3. Off-by-One: < vs <= for Overlap Detection
Do touching intervals overlap?
[1,5] and [5,10] — share point 5.
For Merge Intervals: YES → use <= (merged.back()[1] >= interval[0])
For Meeting Rooms: NO → use < (intervals[i][0] < intervals[i-1][1])
For Burst Balloons: YES → use <= (points[i][0] <= arrowPos means arrow hits)
Read the problem carefully. "Can we reuse the room immediately?" vs
"Does the arrow hit balloons at the boundary?"
4. Not Using max() When Extending the Merged Interval
// WRONG — assumes the new interval always extends further
merged.back()[1] = interval[1];
// RIGHT — the previous interval might fully contain the new one
merged.back()[1] = max(merged.back()[1], interval[1]);
// Example: merging [1,10] with [2,5]
// Wrong gives [1,5], right gives [1,10]
5. Using O(n^2) When O(n log n) Suffices
Comparing every pair of intervals is O(n^2). After sorting, you only need to compare each interval with its neighbors or maintain a small state — giving O(n log n) total.
// WRONG — O(n^2)
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (overlaps(intervals[i], intervals[j])) ...
// RIGHT — O(n log n)
sort(intervals.begin(), intervals.end());
for (int i = 1; i < n; i++)
if (intervals[i][0] < intervals[i-1][1]) ...
6. Not Handling the Empty Input
// WRONG — crashes on empty input
sort(intervals.begin(), intervals.end());
int lastEnd = intervals[0][1]; // index out of bounds!
// RIGHT — guard against empty input
if (intervals.empty()) return {};