When do two intervals overlap?Core idea
For inclusive intervals [start, end], two intervals overlap when each one starts before the other ends:
overlap([a,b], [c,d]) = a <= d && c <= b
Inclusive [1,3] and [3,5]: DO overlap (they share 3)
Half-open [1,3) and [3,5): DO NOT overlapScheduling problems often mean half-open intervals, so ask this before writing any comparison.
Merge intervalsPattern
Sort by start, then walk through. If the next interval overlaps the one you are building, stretch its end; otherwise save it and start a new one.
Merging [1,3], [2,6], [8,10] on a number line
function merge(intervals: number[][]): number[][] {
intervals.sort((a, b) => a[0] - b[0]);
const res: number[][] = [];
for (const [s, e] of intervals) {
const last = res[res.length - 1];
if (res.length && s <= last[1]) {
last[1] = Math.max(last[1], e); // overlap: extend
} else {
res.push([s, e]); // no overlap: start a new one
}
}
return res;
}Insert intervalPattern
The list is already sorted, so there is no need to sort again. Keep everything that ends before the new interval starts, merge everything it overlaps, then add the rest.
function insert(intervals: number[][], newI: number[]): number[][] {
const res: number[][] = [];
let [ns, ne] = newI;
let i = 0;
while (i < intervals.length && intervals[i][1] < ns) {
res.push(intervals[i]); i++; // entirely before
}
while (i < intervals.length && intervals[i][0] <= ne) {
ns = Math.min(ns, intervals[i][0]);
ne = Math.max(ne, intervals[i][1]);
i++; // absorb overlaps
}
res.push([ns, ne]); // the merged interval
while (i < intervals.length) { res.push(intervals[i]); i++; }
return res;
}Meeting roomsPattern
Can one person attend every meeting?
Sort by start and check that no meeting starts before the previous one ends.
function canAttendAll(intervals: number[][]): boolean {
intervals.sort((a, b) => a[0] - b[0]);
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] < intervals[i - 1][1]) return false;
}
return true;
}How many rooms are needed?
The answer is the largest number of meetings happening at the same time. Sort all start times and all end times separately, then sweep with two pointers: a start means one more room in use, an end means one fewer.
function minRooms(intervals: number[][]): number {
const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
const ends = intervals.map(i => i[1]).sort((a, b) => a - b);
let rooms = 0, maxRooms = 0, e = 0;
for (let s = 0; s < starts.length; s++) {
while (e < ends.length && ends[e] <= starts[s]) { rooms--; e++; } // a room frees up
rooms++; // this meeting takes one
maxRooms = Math.max(maxRooms, rooms);
}
return maxRooms;
}Non-overlapping intervals (greedy)Pattern
How many intervals must you remove so the rest never overlap? Greedy rule: always keep the interval that ends earliest, because it leaves the most room for everything after it.
function eraseOverlap(intervals: number[][]): number {
intervals.sort((a, b) => a[1] - b[1]); // sort by END
let end = -Infinity, kept = 0;
for (const [s, e] of intervals) {
if (s >= end) { kept++; end = e; } // fits after the last kept one
}
return intervals.length - kept; // removals
}Interval list intersectionsPattern
Given two sorted lists of intervals, walk both with two pointers. Two intervals intersect on [max(startA, startB), min(endA, endB)]when that range is valid. Then move forward in whichever list's interval ends first.
Which sort key?Compare
| Problem | Sort by | Why |
|---|---|---|
| Merge / insert intervals | Start | Overlapping intervals end up next to each other. |
| Meeting rooms | Start (or starts and ends separately) | You process meetings in the order they begin. |
| Non-overlapping / max activities | End | Finishing early leaves the most room (greedy). |
Common mistakesPitfalls
Frequently asked questionsFAQ
Are interval problems always solvable in O(n log n)?
Yes for the classic set: the O(n log n) bound comes from one sort, and the sweep that follows is O(n). Insert Interval is the exception at O(n) because the input is already sorted. Problems that ask for k-schedules may also push to O(n log n) with a heap.
Do I need a heap for Meeting Rooms II?
No. Sorting starts and ends separately and then sweeping with two pointers gives the same answer in O(n log n) time with O(1) extra space. The heap version keeps each meeting's end time available for later, which reads more naturally when intervals arrive out of order in a follow-up variant.
What does "sort by end time" do differently?
Sorting by end time lets a greedy pass always pick the earliest-finishing compatible interval, which provably maximizes how many you keep. Sorting by start time breaks that invariant and returns a wrong answer on non-overlapping-interval and activity-selection variants, which is exactly why the choice of sort key matters.
Now explain intervals to me out loud
I'll give you interview problems and ask follow-ups, like a real interviewer.