Retrieval: start or end?

Two problems rebuilt cold, plus the one decision that separates these problems from each other.

Key idea

Which key, and why

Almost every interval problem is decided by this one choice, and the reason is always the same: sort by whatever the pass needs to compare against.

Question	Sort by	Because
Does anything conflict	start	conflicts are with the previous interval
Merge overlapping ones	start	connections are between neighbors
Insert one into a sorted set	already sorted	the guarantee makes it linear
Keep as many as possible	end	finishing early frees the resource soonest
How many at once	neither, use events	the answer belongs to a moment

Quick check· 5 min

Which key does this want?

Given a list of jobs with start and end times and one machine, you must report the largest number of jobs that could have been run. What should you sort by?

End time, keeping a job whenever it starts at or after the last kept job finishedStart time, keeping a job whenever it starts after the previous job finishedDuration, shortest first, since short jobs leave the most roomNeither; build an event list and sweep

Problem· 15 min

Merge Intervals, from scratch

You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.

Problem· 20 min

Search in Rotated Sorted Array, from scratch

Intervals

52 / 170

IntervalsLesson 6 of 6About 44 min

Retrieval: start or end?

Two problems rebuilt cold, plus the one decision that separates these problems from each other.

Key idea

Which key, and why

Almost every interval problem is decided by this one choice, and the reason is always the same: sort by whatever the pass needs to compare against.

Question	Sort by	Because
Does anything conflict	start	conflicts are with the previous interval
Merge overlapping ones	start	connections are between neighbors
Insert one into a sorted set	already sorted	the guarantee makes it linear
Keep as many as possible	end	finishing early frees the resource soonest
How many at once	neither, use events	the answer belongs to a moment

Quick check· 5 min

Which key does this want?

Given a list of jobs with start and end times and one machine, you must report the largest number of jobs that could have been run. What should you sort by?

Problem· 15 min

Merge Intervals, from scratch

Problem· 20 min