01 / The idea
The most interesting talk can leave the best day empty.
Deep dive is worth 12 points from 3 to 9. A highest-value-first policy grabs it, then can fit only Opening before it: 16 points in total.
Weighted interval scheduling maximizes the sum of values from non-overlapping intervals. It is not trying to attend the most talks, finish earliest, or pick the single best score.
The compatible sequence Opening, Workshop, Panel, Closing, and Lightning reaches 26. The trick is to make every talk ask about the best schedule that could come before it.
Choose compatible value, not one impressive talk.
selected talk available talk
Put every talk on one timeline.
Each talk has a start, finish, and interest score. A valid schedule may touch at an endpoint, but two talks cannot overlap.
Reduced motion: choose a scene to see its completed state.
Read this scene
Each talk has a start, finish, and interest score. A valid schedule may touch at an endpoint, but two talks cannot overlap.
Seven talks are ready on one timeline. No schedule has been chosen.
Watch and Step through replay the schedule story. Try it changes the talk set and runs the same predecessor-based implementation.
Step through the shortcut, then let the finish-time order expose each talk’s predecessor. The visual keeps interval endpoints visible: a talk ending at 4 can be followed by one starting at 4.
02 / Name the rule
Point to the last talk that can safely come before.
Order talks by finish time. For talk i, let p(i) be the largest
earlier index whose finish is at or before i’s start. Then the best schedule
through i chooses between two complete possibilities:
dp[i] = max(dp[i - 1], value[i] + dp[p(i)])
The first branch skips the talk. The second takes it and jumps back to the best compatible prefix, so overlapping talks never sneak into the same answer.
Sort by finish
Give every later decision a stable prefix of talks that have already ended.
Find p(i)
Binary search finds the last endpoint that does not overlap the current start.
Skip or take
Keep whichever value is larger, then follow the winning links backward.
Why earliest finish is not enoughThat greedy proof has a different objective
Earliest finish is optimal when every talk has equal value and the objective is the number of talks. Once values differ, finishing early can still give up a score worth several shorter talks. The recurrence preserves both options instead of relying on a single safe local choice.
03 / Read the shape
The predecessor array turns overlaps into one jump.
Basic form is solveSchedule with its helpers: sort by finish,
binary-search each predecessor, fill the take-or-skip value array, and backtrack the
selected IDs. In the wild adds the types, input validation, and the
highest-value-first baseline. At the call site compares the weighted result with a highest-value-first baseline
and reports the interest recovered.
solveSchedule: sort talks by finish, binary-search each predecessor, fill the take-or-skip recurrence, and follow predecessor links back to a compatible schedule.
export function solveSchedule(problem: ScheduleProblem): ScheduleResult {
validate(problem);
const orderedTalks = orderByFinish(problem.talks);
const predecessors = orderedTalks.map((_, index) => predecessorFor(orderedTalks, index));
const dp = Array<number>(orderedTalks.length + 1).fill(0);
const snapshots: ScheduleSnapshot[] = [];
for (let index = 1; index <= orderedTalks.length; index += 1) {
const talk = orderedTalks[index - 1];
const predecessor = predecessors[index - 1];
const skip = dp[index - 1];
const take = dp[predecessor + 1] + talk.value;
dp[index] = Math.max(skip, take);
snapshots.push({
talk: talk.id,
index,
predecessor,
bestValue: dp[index],
selectedIds: selectedAt(orderedTalks, predecessors, dp, index),
dp: dp.slice(0, index + 1)
});
}
return {
selectedIds: selectedAt(orderedTalks, predecessors, dp, orderedTalks.length),
totalValue: dp[orderedTalks.length],
orderedTalks,
predecessors,
dp,
snapshots
};
}
export function orderByFinish(talks: Talk[]): Talk[] {
return talks
.map((talk) => ({ ...talk }))
.sort((a, b) => a.end - b.end || a.start - b.start || byId(a.id, b.id));
}
export function predecessorFor(orderedTalks: Talk[], index: number): number {
let low = 0;
let high = index - 1;
let answer = -1;
const start = orderedTalks[index].start;
while (low <= high) {
const middle = Math.floor((low + high) / 2);
if (orderedTalks[middle].end <= start) {
answer = middle;
low = middle + 1;
} else {
high = middle - 1;
}
}
return answer;
}
function selectedAt(
orderedTalks: Talk[],
predecessors: number[],
dp: number[],
count: number
): string[] {
const selected: string[] = [];
let index = count;
while (index > 0) {
const talk = orderedTalks[index - 1];
const predecessor = predecessors[index - 1];
const take = dp[predecessor + 1] + talk.value;
if (take > dp[index - 1]) {
selected.push(talk.id);
index = predecessor + 1;
} else {
index -= 1;
}
}
return selected.reverse();
}func solveSchedule(problem ScheduleProblem) (ScheduleResult, error) {
if err := validate(problem); err != nil {
return ScheduleResult{}, err
}
ordered := orderByFinish(problem.Talks)
predecessors := make([]int, len(ordered))
for index := range ordered {
predecessors[index] = predecessorFor(ordered, index)
}
dp := make([]int, len(ordered)+1)
snapshots := make([]ScheduleSnapshot, 0, len(ordered))
for index := 1; index <= len(ordered); index++ {
talk := ordered[index-1]
predecessor := predecessors[index-1]
skip := dp[index-1]
take := dp[predecessor+1] + talk.Value
if take > skip {
dp[index] = take
} else {
dp[index] = skip
}
snapshots = append(snapshots, ScheduleSnapshot{
Talk: talk.ID,
Index: index,
Predecessor: predecessor,
BestValue: dp[index],
SelectedIDs: selectedAt(ordered, predecessors, dp, index),
DP: append([]int(nil), dp[:index+1]...),
})
}
return ScheduleResult{
SelectedIDs: selectedAt(ordered, predecessors, dp, len(ordered)),
TotalValue: dp[len(ordered)],
OrderedTalks: ordered,
Predecessors: predecessors,
DP: dp,
Snapshots: snapshots,
}, nil
}
func orderByFinish(talks []Talk) []Talk {
ordered := append([]Talk(nil), talks...)
sort.SliceStable(ordered, func(i, j int) bool {
if ordered[i].End != ordered[j].End {
return ordered[i].End < ordered[j].End
}
if ordered[i].Start != ordered[j].Start {
return ordered[i].Start < ordered[j].Start
}
return ordered[i].ID < ordered[j].ID
})
return ordered
}
func predecessorFor(ordered []Talk, index int) int {
low, high, answer := 0, index-1, -1
start := ordered[index].Start
for low <= high {
middle := (low + high) / 2
if ordered[middle].End <= start {
answer = middle
low = middle + 1
} else {
high = middle - 1
}
}
return answer
}
func selectedAt(ordered []Talk, predecessors, dp []int, count int) []string {
selected := []string{}
index := count
for index > 0 {
talk := ordered[index-1]
predecessor := predecessors[index-1]
take := dp[predecessor+1] + talk.Value
if take > dp[index-1] {
selected = append(selected, talk.ID)
index = predecessor + 1
} else {
index--
}
}
for left, right := 0, len(selected)-1; left < right; left, right = left+1, right-1 {
selected[left], selected[right] = selected[right], selected[left]
}
return selected
}Reading the TypeScriptFinish order and binary search
predecessorFor searches only the earlier finish-sorted prefix. Because finishes
are non-decreasing, the last compatible index can be found without scanning every earlier
talk.
Reading the GoThe same recurrence
Go copies the input before sorting, stores predecessors as zero-based indices, and returns the same per-talk snapshots (the film on this page replays the TypeScript ones). Both examples print the selected IDs in finish order, the order the backtrack recovers them in.
What is refusedKeep endpoint semantics explicit
Both versions require non-empty talks with unique lowercase IDs, integer endpoints in a bounded range, and a strictly positive duration. A zero-length talk or a fractional timestamp needs a different contract.
04 / Try a decision
When do two talks stop overlapping?
The predecessor is the boundary that keeps the recurrence honest. Choose the endpoint rule used by the implementation.
05 / Follow the cost
Pay once to order, then jump through the schedule.
| Operation | Time | Extra space | What it assumes |
|---|---|---|---|
| Validate the talk list | O(n) | O(1) | Read every start, finish, and interest value once before making decisions. |
| Order by finish time | O(n log n) | O(n) | A sorted finish order makes earlier compatible prefixes stable and searchable. |
| Find predecessors | O(n log n) | O(n) | Binary search each talk for the last finish at or before its start. |
| Fill and backtrack the DP | O(n²) as shown | O(n²) as shown | Each talk compares skip with take-plus-prefix, and one backtrack recovers the IDs: O(n) time and space. The shown code also backtracks and copies the DP prefix after every talk for the film, which makes it O(n²); without those snapshots it is O(n). |
With n talks, sorting costs O(n log n), predecessor lookup costs O(n log n), and
one DP pass plus one backtrack is O(n), so the algorithm is O(n log n) time and O(n) extra space.
The version shown also backtracks and copies the DP prefix after every talk so the film can replay
it; that costs O(n²) time and space, so drop the snapshots in production.
If talks are already ordered and predecessor links arrive from an index, the ordering cost can disappear. The weighted choices still need the one-dimensional DP state; a greedy earliest-finish pass cannot replace it when values differ.
06 / Give it a real job
Build one attendee’s day.
A conference app has a “Build my day” button. The agenda service takes the day’s talks and
the scores this attendee gave them, calls solveSchedule, and returns the
selected IDs in finish order, which is already the order the attendee will walk through
them.
The solver owns one decision: which talks fit together for the highest total. It doesn’t own the scores, a room that fills up, or the walk between rooms. The endpoint rule treats a talk ending at 4 and one starting at 4 as compatible, which is right in the same room and wrong across a large venue. When the walk matters, the service adds it to each talk’s finish before the call, so the rule stays simple and the schedule stays walkable.
This runs in the agenda service that holds the talk list and each attendee’s scores; nothing in a component computes it, and the agenda screen only draws the day it gets back.
07 / Make the call
Define whether value, count, or room is the objective.
Use weighted interval scheduling when intervals compete for one timeline, values add, and the objective is the highest compatible total. It fits talks, maintenance windows with priorities, and a single operator’s booked work.
Use earliest-finish greedy scheduling when every interval is worth one and the goal is the largest count. Use 0/1 knapsack when the constraint is a capacity budget rather than time overlap.
Three boundaries to rememberSimilar words, different states
- Unweighted intervals: count compatible talks; earliest finish has the greedy proof.
- Weighted intervals: add interest values; take-or-skip needs predecessor links.
- Multiple rooms: allow parallel tracks; one predecessor per talk is no longer enough.
08 / Take the idea with you
Explain the best day without saying “weighted interval scheduling.”
“Line the talks up by when they end. For each talk, find the last one that ends by the time it starts. The best day up to this talk is either the best day without it, or this talk plus the best day up to that earlier one; keep the bigger. At the end, walk back through the choices to name the talks.”
Before moving on, open a calendar with a busy day. Pick the one meeting you value most, and check whether the meetings it overlaps would be worth more together.
Connections to follow nextRelated lessons
- Dynamic programming is the general idea: the best answer for a prefix, built from the best answers for shorter ones.
- Binary search finds each talk’s last compatible predecessor in the finish-sorted list.
- 0/1 knapsack makes the same take-or-skip choice against a budget of room instead of a timeline.