Why does earliest-finish-time beat shortest-duration when picking the most non-overlapping talks?
answer
- what does a chosen talk actually cost you
- only one field affects later choices
- three talks are enough to break it
- a short talk can straddle a seam
- sort by end, sweep once
basics
~20 sChoosing the talk that finishes earliest leaves the largest possible remaining window for everything after it, and that rule is provably optimal. Shortest-duration is not: one short talk can straddle the seam between two longer talks and cost you a slot.
solid answer
~40 sThe objective is the count of talks on one track, not the time filled, so the only thing a choice costs you is the room it consumes going forward. Picking the earliest-finishing compatible talk consumes the least future room, so it can never do worse than any other first pick. Shortest-duration fails on a three-talk counterexample: `0-6`, `5-8`, `7-12`. The shortest is `5-8`, and taking it blocks both of the others, giving one talk where `0-6` plus `7-12` gives two. Earliest-start fails just as easily: with `0-20`, `2-5`, `6-9` it grabs the twenty-hour talk and ends with one instead of two. Sort by end time, sweep once keeping a running last-finish, and the whole thing is `O(n log n)` dominated by the sort.
go deeper
Recall the rule and one counterexample. Be ready to say 'sort by finish time, keep the last finish, accept anything compatible' and to show three intervals where picking the shortest loses a slot.
Explain why the end time is the only quantity a choice spends, and give the complexity as sort-dominated with a one-pass sweep. Expect to be pushed on earliest-start as an alternative and to kill it with an example.
Demonstrate that you check the objective before choosing the rule: count versus occupied time versus weighted value are three different problems, and only the first one this greedy solves. Flag the endpoint convention before writing any comparison.
Own the framing question — what is actually being maximized, and who decided. When a stakeholder wants priorities or fairness folded in, say plainly that the provable rule stops applying and the team is choosing between a heavier exact method and an explicit approximation.
## The problem A conference has one track and a pile of submitted talks, each with a start and an end timestamp. You may schedule any set of talks whose time ranges do not overlap. **Maximize the number of talks scheduled.** Nothing else is being optimized: not the hours filled, not the speakers' seniority, not the audience size. That narrowness is exactly what makes a greedy rule work here, and it is the first thing to say out loud in an interview. ## Why the objective decides the rule Once you accept a talk, the only lasting effect it has on the rest of the schedule is the point in time after which the track becomes free again — its **end**. Its start no longer matters. Its length no longer matters. So among all talks currently compatible with what you have already scheduled, the one that frees the track soonest strictly dominates: any talk that a later choice could have fit after some other pick, it can also fit after this one. This is the intuition behind *earliest finish time first*, and it is the whole idea in one sentence: **the end time is the only resource you spend.** The procedure: sort all talks by end time ascending, walk the sorted list once, keep a variable holding the finish time of the last talk you accepted, and accept the current talk whenever its start is compatible with that finish time. Cost is `O(n log n)` for the sort and `O(n)` for the sweep, so `O(n log n)` overall, with `O(1)` extra space beyond the sort. If the timestamps happen to be small bounded integers (say, minute slots in a single day) you can sort by counting and reach `O(n)`, but the comparison sort is the default answer. ## The two rules that feel right and are wrong **Shortest duration first.** The appeal is obvious: small talks look cheap, so grab lots of them. It fails because a short talk can sit across a seam. Take `0-6`, `5-8`, `7-12`. The shortest is `5-8` at three hours; accepting it conflicts with `0-6` (they overlap from 5 to 6) and with `7-12` (they overlap from 7 to 8), so you finish with one talk. The optimum is `0-6` and `7-12` — two talks, neither of them short. Length was never the right currency. **Earliest start first.** This is how a human queues things, and it fails whenever an early talk is long. With `0-20`, `2-5`, `6-9`, the earliest-starting talk eats the entire day for a single slot; the optimum takes `2-5` and `6-9` for two. A close cousin, *latest start first*, is the mirror image of earliest-finish and is also optimal if you sweep the day backwards — worth knowing so you recognize it when a variant is posed in reverse. **Fewest conflicts first.** This one is more seductive and much more expensive: just computing each talk's conflict count is `O(n log n)` at best and naively `O(n^2)`, and you gain nothing over a rule that is already provably optimal. If you find yourself reaching for it, you have paid more to get no more. ## The trap to keep straight Earliest-finish-time selection maximizes the **number** of talks. It does not maximize occupied time, and it does not maximize any weighted notion of value. With `0-1`, `2-3`, `0-3` available, the greedy schedules two talks covering two hours, while a single `0-3` talk would cover three. If a stakeholder later says "sponsored talks count double," the objective has changed and this greedy is no longer optimal — that variant needs a different technique entirely. Being explicit that greedy optimality is attached to a specific objective is the difference between reciting the rule and understanding it. ## What to say in the room Name the rule, give the one-line reason ("the end time is the only thing a choice costs you"), produce a three-interval counterexample for shortest-duration and one for earliest-start, and state the complexity as sort-dominated. If the interviewer pushes, mention that the endpoint convention — whether a talk ending at 14:00 conflicts with one starting at 14:00 — has to be pinned down before you write the comparison, because it silently changes the answer.
- Does this greedy also maximize the total scheduled hours?No. It maximizes the count only. With `0-1`, `2-3` and `0-3` on offer, it schedules two talks filling two hours, while the single `0-3` talk would fill three. Maximizing occupied time is a different objective with a different answer, and saying so unprompted shows you know greedy optimality is always attached to one specific objective.
- What is the running time, and which part dominates?`O(n log n)`, entirely from sorting by end time; the selection sweep is a single `O(n)` pass with `O(1)` extra state. If the endpoints are small bounded integers you can sort them by counting and get `O(n)` overall, but a comparison sort is the default assumption unless the interviewer says otherwise.
- Is there a second rule that is also optimal for this objective?Yes — sweeping the day backwards and repeatedly taking the latest-starting compatible talk is the mirror image and is equally optimal. Recognizing it matters because interviewers sometimes pose the problem in reverse ("schedule from the end of the day"), and candidates who only memorized "sort by end" freeze on the variant.
Booking a shared meeting room: the only thing that matters to the next person is when you hand the key back, not how long you held it or how early you grabbed it.
saying these in an interview costs you the question
- Says shortest talks first fits the most talks
- Sorts by start time and calls it optimal
- Claims the greedy maximizes total scheduled hours
- Thinks the rule still holds when talks carry values
- Cannot produce any three-interval counterexample