Algorithms from zero
Interval scheduling: activity selection and merging intervals
You have one conference room and a stack of meeting requests, each with a start and end time. Many of them clash. You cannot fit them all, so you want to fit the most you can. Your gut says: grab the meeting that starts earliest, then the next one that fits, and so on. That gut feeling is wrong, and it is wrong in a way that costs you meetings. The right move is almost the opposite—care about when each meeting ends, not when it starts. One sort, one pass, provably optimal. This lesson teaches that greedy, its close cousin “merge the overlapping intervals,” and the room-counting variant—three problems that show up constantly and all live or die on what you sort by.
After this lesson you can solve the three classic interval problems. (1) Activity selection / interval scheduling maximization: pick the largest set of non-overlapping intervals by sorting on earliest finish time and greedily taking each interval whose start is at or after the last taken interval’s finish. You can explain why finish time is the right key and give a concrete counterexample showing that sorting by start time or by shortest duration fails. (2) Merge intervals: collapse a set of intervals into the minimal set of disjoint ones by sorting on start and sweeping, extending the current run while the next interval overlaps it. (3) Minimum rooms (“meeting rooms II”): find the peak number of simultaneously active intervals by sorting the start times and end times separately and sweeping a two-pointer counter. You can state that all three are O(n log n), dominated by the sort, with O(n) or O(1) extra work in the sweep. You connect this back to the exchange argument from lesson 02: earliest-finish is provably optimal because any optimal solution can be rewritten to start with the earliest-finishing interval without losing count.
Problem 1: pick the most non-overlapping intervals
You are given intervals like [start, end]. Two intervals overlap if one starts before the other ends. You want the largest set with no overlaps. (Think: the most meetings you can fit in one room, the most jobs one machine can run.)
The winning greedy is one line of intuition: sort by finish time, then walk left to right taking any interval that starts at or after the last one you took ended.
sorted by finish: [1,4] [3,5] [2,6] [5,7] [6,8]
====
take [1,4] ---- lastEnd = 4
[3,5] starts 3 < 4 skip (overlaps)
[2,6] starts 2 < 4 skip (overlaps)
[5,7] starts 5 >= 4 take, lastEnd = 7
[6,8] starts 6 < 7 skip (overlaps)
result: { [1,4], [5,7] } -> 2 intervalsWhy finish time? The interval that finishes earliest leaves the most room behind it for everything else. Taking it can never hurt you: whatever optimal solution exists, you can swap its first interval for the earliest-finishing one without creating any new overlap and without losing count. That is exactly the exchange argument from lesson 02—the earliest-finish choice is “safe,” so greedily repeating it is optimal.
The tempting wrong greedies
- Sort by start time. A meeting that starts at 9:00 and runs all day would get grabbed first and block everything. Earliest start says nothing about how much room is left.
- Sort by shortest duration. This feels clever—small meetings should pack tightly—but a single short interval can sit right in the middle and block two longer ones that did not overlap each other. Counterexample:
[0,4],[3,5],[4,8]. The shortest is[3,5](length 2). Take it and both[0,4]and[4,8]now clash with it, so you get 1. But[0,4]and[4,8]do not overlap each other, so the real answer is 2. Earliest-finish takes[0,4](finishes at 4), then[4,8](starts at 4) and gets 2. Shortest-duration loses.
The lesson: with intervals, the right thing to sort by is rarely the obvious thing. Finish time wins for maximization.
Problem 2: merge overlapping intervals
Different goal: given overlapping intervals, collapse them into the fewest disjoint intervals that cover the same ground. [1,3], [2,6], [8,10], [15,18] becomes [1,6], [8,10], [15,18].
Here you sort by start time and sweep:
sorted by start: [1,3] [2,6] [8,10] [15,18]
current run = [1,3]
[2,6]: 2 <= 3 (overlaps) -> extend run to [1,6]
[8,10]: 8 > 6 (gap) -> close [1,6], open new run [8,10]
[15,18]: 15 > 10 (gap) -> close [8,10], open new run [15,18]
result: [1,6] [8,10] [15,18]Sorting by start guarantees that once you pass an interval, nothing later can reach back behind the current run’s start, so you only ever compare against the one run you are currently building. That is what makes a single left-to-right pass correct.
Problem 3: minimum number of rooms (“meeting rooms II”)
Now you have unlimited time but want the fewest rooms so no two meetings share a room. The answer is the maximum number of meetings active at the same instant—the peak overlap.
Sort all the start times and all the end times into two separate lists, then sweep both with a two-pointer counter: each time the next event is a start, a meeting begins, so add a room and track the peak; each time the next event is an end, a meeting finished, so free a room.
starts: 0 5 15 ends: 10 20 30
start 0 -> rooms 1 (peak 1)
start 5 -> rooms 2 (peak 2) [0,30] and [5,10] both active
end 10 -> rooms 1
start 15 -> rooms 2 (peak 2)
...
answer = peak = 2All three problems are the same shape: sort the intervals on the right key, then make one sweep. The sort is the expensive part.
Activity selection: sort by earliest finish, then take what fits
The state to carry is one number: lastEnd, the finish time of the most recent interval you took. An interval is takeable exactly when its start is at or after lastEnd.
1
function maxActivities(intervals) {
2
// Sort by earliest FINISH time - the safe greedy key
3
const sorted = [...intervals].sort((a, b) => a[1] - b[1]);
4
let count = 0;
5
let lastEnd = -Infinity; // nothing taken yet
6
const chosen = [];
7
for (const [start, end] of sorted) {
8
if (start >= lastEnd) { // starts after the last taken one finishes
9
count++;
10
lastEnd = end; // this interval is now the latest taken
11
chosen.push([start, end]);
12
}
13
}
14
return { count, chosen };
15
}
- L3 Sort by index 1 (the end time). This single line is what makes the whole greedy optimal.
- L5 lastEnd starts at -Infinity so the very first interval always passes the test.
- L8 The greedy test: an interval fits if it starts at or after the last finish. '>=' allows back-to-back touching intervals like [1,4] then [4,8].
- L10 Commit to this interval: bump the count and advance lastEnd to its finish.
- L11 Record it (optional - drop 'chosen' if you only need the count).
Running it
Eleven activities; the greedy finds four that never overlap.
The shortest-duration greedy is wrong — proof by counterexample
Run the wrong strategy against the right one on the trap input [0,4], [3,5], [4,8]. The shortest interval [3,5] sits in the middle and blocks both others.
Two against one. The shortest interval looked harmless and cost a whole slot. Finish time is the only key that is provably safe.
Merge intervals: sort by start, sweep, extend the current run
Note Math.max(last[1], end) on the extend line: without it, a fully nested interval like [2,3] inside [1,4] would wrongly shrink the run to [1,3]. The “nested” case proves the guard works—the run stays [1,4].
Let us trace activity selection on [[3,5], [1,4], [5,7], [2,6], [6,8]] (deliberately unsorted, so the sort step is visible). The greedy keeps one piece of state, lastEnd, and the verdict is “take” when start >= lastEnd.
1
const sorted = intervals.sort((a, b) => a[1] - b[1]);
2
let lastEnd = -Infinity;
3
for (const [start, end] of sorted) {
4
if (start >= lastEnd) {
5
take(start, end); lastEnd = end;
6
}
7
}
Time: O(n log n) — the sort dominates
Every one of the three algorithms has the same cost breakdown:
sort the n intervals O(n log n) <- the expensive step
one linear sweep O(n)
total O(n log n)The greedy sweep itself is a single pass: each interval is looked at once, with O(1) work (a comparison and maybe an update). That is O(n). The only reason the whole thing is not O(n) is the sort, which is O(n log n). So for all three:
activity selection O(n log n) (sort by finish)
merge intervals O(n log n) (sort by start)
minimum rooms O(n log n) (sort starts and ends)This is the signature of interval greedies: the sort is the algorithm’s whole cost. If the intervals arrive already sorted on the key you need (sometimes true for event streams), the sweep alone is O(n).
Space: O(n) or O(1) beyond the sort
- Activity selection needs only
lastEndand a counter: O(1) extra (O(n) if you also collect the chosen list). - Merge intervals builds the output list, which is at most n intervals: O(n).
- Minimum rooms holds the two sorted arrays of start/end times: O(n).
The sort may use O(log n) to O(n) auxiliary space depending on the implementation, but the dominant story is: cheap sweep, one sort, O(n log n) time.
To pick the maximum number of non-overlapping intervals, what should you sort by?
Why is 'sort by shortest duration' a wrong greedy for maximizing non-overlapping intervals?
For merging overlapping intervals into the fewest disjoint ones, what is the right approach?
The 'minimum number of rooms' (meeting rooms II) answer equals which quantity?
Why are all three interval algorithms O(n log n)?
Given intervals [1,4], [2,5], [7,9], what is the minimum number of rooms needed (peak overlap)?
Given intervals [0,2], [1,3], [2,4], [3,5], how many non-overlapping intervals can you pick at most?
Common mistake
Mistake: sorting by start time for the maximization problem. Sort-by-start is correct for merging intervals, so it is easy to reach for it everywhere. But for picking the most non-overlapping intervals it fails: a meeting that starts earliest but runs forever gets grabbed first and blocks everything after it. The keys are problem-specific—finish time for maximization, start time for merging. Mixing them up silently returns a wrong-but-plausible answer.
Edge cases
Touching endpoints: is [1,4] then [4,8] an overlap? It depends on whether intervals are half-open. In most scheduling problems they are: a meeting ending at 4:00 and one starting at 4:00 do not clash, so the test is start >= lastEnd (use >=, allowing back-to-back). If the endpoints are inclusive and touching counts as a conflict, use start > lastEnd. For merge intervals the same choice appears: start <= last[1] merges touching intervals into one run; start < last[1] keeps them separate. Decide the endpoint convention first, then pick >/>= accordingly—a single wrong comparison shifts every answer by one.
Why this works
Why is earliest-finish provably optimal? This is the exchange argument from lesson 02. Suppose some optimal solution does not start with the earliest-finishing interval f. Its first interval g finishes no earlier than f (since f finishes earliest of all). Swap g for f: because f finishes at or before g, f cannot overlap anything that came after g, so the swap stays valid and keeps the same count. Repeating the argument, you can rebuild any optimal solution to begin with the greedy’s choice. The greedy choice is therefore “safe,” and a sequence of safe choices is optimal. This is the heart of why greedy works here and not for, say, coin change with arbitrary denominations.
More practice
The interval-greedy checklist. (1) What are you optimizing—most intervals, fewest merged runs, fewest rooms? (2) Pick the sort key: finish time for “most non-overlapping,” start time for “merge,” start-and-end lists for “fewest rooms.” (3) Carry the minimal state: lastEnd for selection, the current run for merge, a running counter and peak for rooms. (4) One sweep, O(1) work per interval. (5) Decide the endpoint convention (> vs >=) up front. The cost is always O(n log n), and almost all of it is the sort.
Describe how to maximize the number of non-overlapping intervals, why that greedy is correct, how it differs from merging intervals, and the complexity of these interval algorithms.
Three interval problems, all solved by sort on the right key, then one sweep.
Activity selection (most non-overlapping intervals): sort by earliest finish time, take each interval whose start is >= lastEnd, advance lastEnd. Correct by the exchange argument: the earliest-finishing interval is always a safe choice because it leaves the most room behind it.
Wrong greedies to avoid: sort-by-start (an early-but-long interval blocks everything) and sort-by-shortest-duration (a short interval in the middle blocks two non-overlapping neighbors—[0,4],[3,5],[4,8] gives 1 instead of 2).
Merge intervals (fewest disjoint runs): sort by start, sweep, extend the current run while start <= last[1] (use Math.max on the end to survive nested intervals), else open a new run.
Minimum rooms (meeting rooms II): the answer is the peak overlap. Sort starts and ends separately, sweep a two-pointer counter—add a room on each start, free one on each end, track the maximum.
Complexity: all three are O(n log n), with the sort dominating an O(n) sweep. Space is O(1) (selection, count only) to O(n) (merge output, room arrays). The endpoint convention (> vs >=, < vs <=) decides whether touching intervals count as overlapping—choose it before you write the comparison.
The recurring lesson of interval greedies: the hard part is choosing what to sort by, not the sweep. Get the key right and the rest is one linear pass.