01 / The idea
One festival day asks three kinds of question.
The gate counts the main-stage crowd every hour: people who arrived minus people who left, in hundreds. The organizers want the stretch of hours when the crowd grew most, because that is when the stewards were short. The main stage has five talk proposals with fixed times and room for one at a time, and the program wants as many as fit. And a 10-minute gap before the keynote has to be filled exactly with lightning talks of 8, 6, 5, and 4 minutes.
Each question has an obvious first program: try every stretch, every set of talks, every combination of lightning talks. Each also has a shortcut, and each shortcut is safe only for a reason. Divide and conquer solves independent halves and combines them. Greedy makes one local choice it can prove never hurts. Backtracking makes a choice, checks it, and undoes it when it leads nowhere.
02 / Name the rule
Split and combine, take the earliest finish, undo a dead end.
Split. The stretch when the crowd grew most lies in the morning half, in the afternoon half, or across the middle, where it is the best end of the morning joined to the best start of the afternoon. Solve both halves the same way and combine.
best(left..right) = max(
best(left..mid), best(mid+1..right),
bestSuffix(left..mid) + bestPrefix(mid+1..right)
)Choose. To fit the most talks, sort them by end time and accept a talk when it starts at or after the last accepted talk ends. The proof is an exchange: if a best schedule starts with a later-finishing talk, swap in the one that ends first and everything after it still fits.
sort talks by end
for talk in order:
if talk.start >= lastEnd: accept talkUndo. To fill 10 minutes, decide for each lightning talk whether it goes in, then move to the next. When the minutes left cannot be filled, take the last talk back out and try the other branch. The invariant is restoration: after a branch fails, the chosen talks and the minutes left are exactly what they were before it.
Where each shortcut stops being safeThe proof depends on the question
Earliest finish is safe because every talk counts the same. Give talks different values and it can pick a worse schedule; that version is a dynamic-programming problem. Taking the longest lightning talk that fits looks like the same kind of rule, and it fails here: 8 minutes leaves a 2-minute hole no talk fits.
Backtracking may reach the same minutes left through different choices. When those repeats are the problem, dynamic programming stores each answer once.
03 / Follow one operation
See the split, the safe choice, and the undo.
Before you watch, predict which hours the crowd grew most in, and which lightning talk gets taken back out. The animation replays one recorded run per strategy: the day split in half and combined, the talks accepted and rejected by finish time, then the 8-minute talk tried and undone before 6 + 4 fills the gap. Try it lets you run each strategy against its baseline.
Split, choose, or undo.
hourly crowd change, in hundreds
Find when the crowd grew most
0 splitsNo best run yet
Split hours 0–7 at 3. Step 1.
Split hours 0–7 at 3. Step 1.
Follow the next structural decision.
Split hours 0–7 at 3. Step 1.
Reduced motion: choose a scene to see its completed state.
Read this scene
Split hours 0–7 at 3. Step 1.
Split hours 0–7 at 3. Step 1.
Find the hours when the crowd grew most.
Watch restarts when you return. Step through keeps the selected trace. Try it measures a fresh strategy on the festival fixtures.
04 / Read the shape
Keep the baseline beside the strategy.
Basic form is the three algorithms: maxSubarray with its
split-and-combine summaries, selectTalks with the earliest-finish loop, and chooseBundle with its include-or-skip search and undo, each beside a simpler
baseline mode. In the wild gives each a small contract and plans one day.
The baseline is what makes the shortcut testable: the split must agree with a scan, the greedy schedule with brute force on small inputs, and backtracking must fill the gap where largest-first cannot.
maxSubarray, selectTalks, and chooseBundle: the split-and-combine summaries, the earliest-finish loop, and the include-or-skip search with its undo, each beside a simpler baseline mode.
// Divide and conquer keeps the best subarray in the left half, right half, or across the split.
export function maxSubarray(
values: readonly number[],
mode: ArrayMode = 'divide-and-conquer',
trace = false
): ArrayEvaluation {
const checked = validateValues(values);
const steps: ArrayStep[] = [];
if (mode === 'scan') {
let running = checked[0];
let best = checked[0];
let runningStart = 0;
let bestStart = 0;
let bestEnd = 0;
for (let index = 1; index < checked.length; index++) {
if (running + checked[index] < checked[index]) {
running = checked[index];
runningStart = index;
} else running += checked[index];
if (running > best) {
best = running;
bestStart = runningStart;
bestEnd = index;
}
if (trace) steps.push({ kind: 'scan', index, running, best });
}
return {
kind: 'array',
mode,
values: checked,
bestSum: best,
start: bestStart,
end: bestEnd,
work: Math.max(0, checked.length - 1),
steps
};
}
let work = 0;
type Segment = {
total: number;
best: number;
start: number;
end: number;
prefix: number;
prefixEnd: number;
suffix: number;
suffixStart: number;
};
function solve(left: number, right: number): Segment {
if (left === right)
return {
total: checked[left],
best: checked[left],
start: left,
end: right,
prefix: checked[left],
prefixEnd: left,
suffix: checked[left],
suffixStart: left
};
const mid = Math.floor((left + right) / 2);
if (trace) steps.push({ kind: 'split', left, right, mid });
const a = solve(left, mid);
const b = solve(mid + 1, right);
let prefix = a.prefix;
let prefixEnd = a.prefixEnd;
if (a.total + b.prefix > prefix) {
prefix = a.total + b.prefix;
prefixEnd = b.prefixEnd;
}
let suffix = b.suffix;
let suffixStart = b.suffixStart;
if (b.total + a.suffix > suffix) {
suffix = b.total + a.suffix;
suffixStart = a.suffixStart;
}
const crossing = a.suffix + b.prefix;
let best = a;
if (b.best > best.best) best = b;
if (crossing > best.best)
best = {
total: a.total + b.total,
best: crossing,
start: a.suffixStart,
end: b.prefixEnd,
prefix,
prefixEnd,
suffix,
suffixStart
};
work += 1;
if (trace)
steps.push({ kind: 'merge', left, right, start: best.start, end: best.end, sum: best.best });
return {
total: a.total + b.total,
best: best.best,
start: best.start,
end: best.end,
prefix,
prefixEnd,
suffix,
suffixStart
};
}
const result = solve(0, checked.length - 1);
return {
kind: 'array',
mode,
values: checked,
bestSum: result.best,
start: result.start,
end: result.end,
work,
steps
};
}
// Earliest finish leaves the largest possible suffix for the next compatible talk.
export function selectTalks(
talks: readonly Talk[],
mode: TalkMode = 'greedy',
trace = false
): TalkEvaluation {
const checked = validateTalks(talks);
const steps: TalkStep[] = [];
if (mode === 'brute-force') {
if (checked.length > 20)
throw new RangeError('brute-force talk search accepts at most 20 entries');
let selected: number[] = [];
let work = 0;
for (let mask = 0; mask < 1 << checked.length; mask++) {
const candidate = checked
.map((_, index) => index)
.filter((index) => mask & (1 << index))
.sort((a, b) => checked[a].start - checked[b].start);
if (
candidate.every(
(index, position) =>
position === 0 || checked[index].start >= checked[candidate[position - 1]].end
)
) {
work++;
if (candidate.length > selected.length) selected = candidate;
}
}
return { kind: 'talks', mode, talks: checked, selected, work, steps };
}
const order = checked
.map((_, index) => index)
.sort((a, b) => checked[a].end - checked[b].end || checked[a].start - checked[b].start);
let end = -Infinity;
const selected: number[] = [];
for (const index of order) {
const talk = checked[index];
const accepted = talk.start >= end;
if (accepted) {
selected.push(index);
end = talk.end;
}
if (trace)
steps.push({
kind: 'consider',
index,
name: talk.name,
start: talk.start,
end: talk.end,
accepted,
reason: accepted
? 'starts at or after the last accepted talk ends'
: 'starts before the last accepted talk ends'
});
}
return { kind: 'talks', mode, talks: checked, selected, work: order.length, steps };
}
// Backtracking explores include/skip branches and undoes a choice when its remaining target dies.
export function chooseBundle(
values: readonly number[],
target: number,
mode: BundleMode = 'backtracking',
trace = false
): BundleEvaluation {
const checked = validateValues(values);
validateTarget(target);
const steps: BundleStep[] = [];
if (mode === 'greedy') {
let remaining = target;
const selected: number[] = [];
const order = checked.map((_, index) => index).sort((a, b) => checked[b] - checked[a]);
for (const index of order) {
if (checked[index] <= remaining) {
remaining -= checked[index];
selected.push(index);
if (trace) steps.push({ kind: 'choose', index, value: checked[index], remaining });
}
}
if (remaining === 0 && trace)
steps.push({ kind: 'complete', indexes: selected, total: target });
if (remaining !== 0 && trace) steps.push({ kind: 'miss' });
return {
kind: 'bundle',
mode,
values: checked,
target,
selected: remaining === 0 ? selected : null,
work: order.length,
steps
};
}
let work = 0;
let answer: number[] | null = null;
// One selection, shared by every branch: a choice is pushed before its branch and popped
// after the branch fails, so the next branch starts from exactly the state before it.
const selected: number[] = [];
function search(index: number, remaining: number): boolean {
work++;
if (remaining === 0) {
answer = [...selected];
if (trace) steps.push({ kind: 'complete', indexes: [...selected], total: target });
return true;
}
if (index === checked.length || remaining < 0) {
if (trace) steps.push({ kind: 'miss' });
return false;
}
if (checked[index] <= remaining) {
if (trace)
steps.push({
kind: 'choose',
index,
value: checked[index],
remaining: remaining - checked[index]
});
selected.push(index);
if (search(index + 1, remaining - checked[index])) return true;
selected.pop();
if (trace) steps.push({ kind: 'backtrack', index, value: checked[index], remaining });
}
if (trace) steps.push({ kind: 'skip', index, value: checked[index], remaining });
return search(index + 1, remaining);
}
search(0, target);
return { kind: 'bundle', mode, values: checked, target, selected: answer, work, steps };
}func MaxSubarray(values []int, mode ArrayMode, trace bool) (ArrayEvaluation, error) {
checked, err := validateValues(values)
if err != nil {
return ArrayEvaluation{}, err
}
result := ArrayEvaluation{Mode: mode, Values: checked}
if mode == Scan {
running, best := checked[0], checked[0]
runningStart, bestStart, bestEnd := 0, 0, 0
for index := 1; index < len(checked); index++ {
if running+checked[index] < checked[index] {
running = checked[index]
runningStart = index
} else {
running += checked[index]
}
if running > best {
best, bestStart, bestEnd = running, runningStart, index
}
if trace {
result.Steps = append(result.Steps, ArrayStep{Kind: "scan", Index: index, Running: running, Best: best})
}
}
result.BestSum, result.Start, result.End, result.Work = best, bestStart, bestEnd, len(checked)-1
return result, nil
}
work := 0
var solve func(int, int) segment
solve = func(left, right int) segment {
if left == right {
return segment{total: checked[left], best: checked[left], start: left, end: right, prefix: checked[left], prefixEnd: left, suffix: checked[left], suffixStart: left}
}
mid := (left + right) / 2
if trace {
result.Steps = append(result.Steps, ArrayStep{Kind: "split", Left: left, Right: right, Mid: mid})
}
a, b := solve(left, mid), solve(mid+1, right)
prefix, prefixEnd := a.prefix, a.prefixEnd
if a.total+b.prefix > prefix {
prefix, prefixEnd = a.total+b.prefix, b.prefixEnd
}
suffix, suffixStart := b.suffix, b.suffixStart
if b.total+a.suffix > suffix {
suffix, suffixStart = b.total+a.suffix, a.suffixStart
}
best := a
if b.best > best.best {
best = b
}
crossing := a.suffix + b.prefix
if crossing > best.best {
best = segment{total: a.total + b.total, best: crossing, start: a.suffixStart, end: b.prefixEnd}
}
work++
if trace {
result.Steps = append(result.Steps, ArrayStep{Kind: "merge", Left: left, Right: right, Start: best.start, End: best.end, Sum: best.best})
}
return segment{total: a.total + b.total, best: best.best, start: best.start, end: best.end, prefix: prefix, prefixEnd: prefixEnd, suffix: suffix, suffixStart: suffixStart}
}
answer := solve(0, len(checked)-1)
result.BestSum, result.Start, result.End, result.Work = answer.best, answer.start, answer.end, work
return result, nil
}
func SelectTalks(talks []Talk, mode TalkMode, trace bool) (TalkEvaluation, error) {
checked, err := validateTalks(talks)
if err != nil {
return TalkEvaluation{}, err
}
result := TalkEvaluation{Mode: mode, Talks: checked}
if mode == BruteForce {
if len(checked) > 20 {
return TalkEvaluation{}, fmt.Errorf("brute-force talk search accepts at most 20 entries")
}
var selected []int
for mask := uint64(0); mask < uint64(1)<<len(checked); mask++ {
candidate := make([]int, 0)
for index := range checked {
if mask&(uint64(1)<<index) != 0 {
candidate = append(candidate, index)
}
}
sort.Slice(candidate, func(i, j int) bool { return checked[candidate[i]].Start < checked[candidate[j]].Start })
valid := true
for index := 1; index < len(candidate); index++ {
if checked[candidate[index]].Start < checked[candidate[index-1]].End {
valid = false
}
}
if valid {
result.Work++
if len(candidate) > len(selected) {
selected = candidate
}
}
}
result.Selected = selected
return result, nil
}
order := make([]int, len(checked))
for index := range order {
order[index] = index
}
sort.Slice(order, func(i, j int) bool {
if checked[order[i]].End == checked[order[j]].End {
return checked[order[i]].Start < checked[order[j]].Start
}
return checked[order[i]].End < checked[order[j]].End
})
end := -1
for _, index := range order {
talk := checked[index]
accepted := talk.Start >= end
if accepted {
result.Selected = append(result.Selected, index)
end = talk.End
}
result.Work++
if trace {
result.Steps = append(result.Steps, TalkStep{Kind: "consider", Index: index, Name: talk.Name, Start: talk.Start, End: talk.End, Accepted: accepted, Reason: map[bool]string{true: "starts at or after the last accepted talk ends", false: "starts before the last accepted talk ends"}[accepted]})
}
}
return result, nil
}
func ChooseBundle(values []int, target int, mode BundleMode, trace bool) (BundleEvaluation, error) {
checked, err := validateValues(values)
if err != nil {
return BundleEvaluation{}, err
}
if err := validateTarget(target); err != nil {
return BundleEvaluation{}, err
}
result := BundleEvaluation{Mode: mode, Values: checked, Target: target}
if mode == BundleGreedy {
order := make([]int, len(checked))
for index := range order {
order[index] = index
}
sort.Slice(order, func(i, j int) bool { return checked[order[i]] > checked[order[j]] })
remaining := target
for _, index := range order {
if checked[index] <= remaining {
remaining -= checked[index]
result.Selected = append(result.Selected, index)
if trace {
result.Steps = append(result.Steps, BundleStep{Kind: "choose", Index: index, Value: checked[index], Remaining: remaining})
}
}
result.Work++
}
result.HasSelection = remaining == 0
if trace && result.HasSelection {
result.Steps = append(result.Steps, BundleStep{Kind: "complete", Indexes: result.Selected, Total: target})
}
if trace && !result.HasSelection {
result.Steps = append(result.Steps, BundleStep{Kind: "miss"})
}
if !result.HasSelection {
result.Selected = nil
}
return result, nil
}
var answer []int
// One selection, shared by every branch: a choice is appended before its branch and removed
// after the branch fails, so the next branch starts from exactly the state before it.
selected := []int{}
var search func(int, int) bool
search = func(index, remaining int) bool {
result.Work++
if remaining == 0 {
answer = append([]int{}, selected...)
if trace {
result.Steps = append(result.Steps, BundleStep{Kind: "complete", Indexes: answer, Total: target})
}
return true
}
if index == len(checked) {
if trace {
result.Steps = append(result.Steps, BundleStep{Kind: "miss"})
}
return false
}
if checked[index] <= remaining {
if trace {
result.Steps = append(result.Steps, BundleStep{Kind: "choose", Index: index, Value: checked[index], Remaining: remaining - checked[index]})
}
selected = append(selected, index)
if search(index+1, remaining-checked[index]) {
return true
}
selected = selected[:len(selected)-1]
if trace {
result.Steps = append(result.Steps, BundleStep{Kind: "backtrack", Index: index, Value: checked[index], Remaining: remaining})
}
}
if trace {
result.Steps = append(result.Steps, BundleStep{Kind: "skip", Index: index, Value: checked[index], Remaining: remaining})
}
return search(index+1, remaining)
}
search(0, target)
result.Selected, result.HasSelection = answer, answer != nil
return result, nil
}Reading the TypeScriptTraceable structural decisions
Each evaluator validates at its boundary and can record its splits, considerations, or branch steps. The trace comes from the same run that returns the answer.
Reading the GoExplicit slices and structs
Go copies input slices and returns structs. The recursive gap search appends to one shared selection and reslices it after a failed branch; the answer is copied out when a branch completes, so later undoing cannot change it.
What would I normally use in application code?Mostly a library that already made the choice
Rarely your own. Your language’s sort already divides and merges. Scheduling and packing problems with more rules than these usually belong to a solver. Write the search yourself when the choices are few and the rules are yours, as with this festival.
05 / Try a decision
Pick the rule you could defend in code review.
Several rules sound reasonable for filling the stage. Decide which one has a proof before the feedback tells you.
06 / Follow the cost
The name of the strategy does not set the cost.
Here is every operation at a glance, with n hours, talks, or lightning talks. The rest of this section is about why the split here is linear and the search is not.
| Operation | Time | Extra space | What it assumes |
|---|---|---|---|
| Maximum subarray scan | O(n) | O(1) | Keep the best run ending at the current position; the simple baseline is often enough. |
| Divide-and-conquer maximum subarray | O(n) | O(log n) | Each half returns its total, best run, best prefix, and best suffix, so combining is constant work: n − 1 combines. Scanning for the crossing run instead would make it O(n log n). |
| Greedy interval scheduling | O(n log n) | O(n) | Sort by finish time, then scan once; the sort dominates and the exchange proof makes the local choice safe. |
| Backtracking to fill a gap | O(2ⁿ) | O(n) | The worst case visits include/skip branches; the call path is linear, and pruning can help actual inputs. |
The split carries four numbers up from each half: its total, its best stretch, its best start, and its best end. Combining two halves is then constant work, so eight hours take seven combines, the same order as a single scan. Greedy is dominated by the sort. Backtracking can visit every include-or-skip branch, 2ⁿ of them, and it stays fast here only because four talks make sixteen branches and a full gap stops the search early.
07 / Give it a real job
Plan the day with the rules the organizers actually have.
In a real planner, the gate’s hourly counts arrive from the ticket scanners, the talk slots from the program committee, and the gap from whatever ran short. The planner answers each question with the strategy its rule allows, and it keeps the baseline in its tests.
What the examples leave out is a decision too. Talks here are all worth the same; real ones have speakers who can only come at certain hours, and a talk that runs over moves everything after it. The gap search stops at the first exact fill, where an organizer might prefer the fill with fewer speaker changes. Those rules change which strategy is safe.
In frontend code these strategies mostly arrive inside something else: the sort behind a table, the regular expression in a form validator, the layout engine fitting text into lines. They are worth recognizing there, and rarely worth writing.
08 / Make the call
Let what you can prove choose the strategy.
Reach for divide and conquer when halves can be solved independently and combining them is cheap. Reach for greedy when an exchange argument shows the local choice never hurts. Reach for backtracking when the choices are few enough to explore and every branch can put back what it changed.
Look elsewhere when the question changes. A single pass will do: the scan. Talks with different values, or a search that keeps reaching the same minutes left: dynamic programming. Too many choices to explore: a solver or a good-enough heuristic, said out loud as one.
09 / Take the idea with you
Explain it without saying “divide and conquer,” “greedy,” or “backtracking.”
“I found the busiest stretch by solving each half of the day and checking the stretch that crosses the middle. I filled the stage by always taking the talk that ends first, because swapping it in never costs a later talk. I filled the gap by trying a talk, and taking it back out when the minutes left could not be filled.” That describes the mechanisms. The names are what you call them in a review.
Before moving on, explain three things without the names: why the best stretch can cross the middle, why earliest finish is safe but longest-first is not, and what the search puts back after a dead end. Then find a loop in your own code that tries every combination, and ask which of the three it could become.
Connections to follow nextRelated lessons
- Recursion is the call structure all three strategies lean on.
- Dynamic programming stores repeated answers when a search keeps meeting the same state.
- Sorting is divide and conquer you already use, and the setup the greedy schedule needs.