Intervals
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 |
Tip
And the recurring decision
Whether touching counts as overlapping has come up in every lesson of this unit. It is decided by the problem, not by the technique, and it is the single most common reason an interval solution is off by exactly the cases you did not test.
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?
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.
Search in Rotated Sorted Array, 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.