mediumCodingEntryMidSenior
Given a list of meetings with start and end times, pick the largest set of them that do not overlap.
Sort by finishing time and take every meeting that starts no earlier than the last one you took. Earliest start and shortest duration both look reasonable and both give provably smaller answers, and the exchange argument for earliest finish is what the question is really asking for.
4 min readUpdated 2026-08-15Target archetype: Big Tech, Enterprise Captive, Product Startup
Answer
Short answer
Sort by finishing time and take every meeting that starts no earlier than the last one you took. Earliest start and shortest duration both look reasonable and both can produce smaller answers; earliest finish is safe because an exchange argument can swap it into an optimal schedule without reducing the count.
Was this answer helpful?
Likely follow-ups
- Each meeting now carries a value and you want the greatest total value. Does the greedy survive?
- You have k rooms rather than one. What is the largest set you can hold now?
- Return which meetings you selected, not just how many.
- The meetings arrive one at a time and you must accept or reject immediately. How much worse can you do?
Related questions
- How do you know a greedy choice is safe and not merely plausible?mediumAlso on greedy and exchange-argument4 min
- Shipping packages within D days minimises a maximum. Now place m sensors at fixed positions so the closest pair is as far apart as possible. What changes in the binary search?mediumAlso on greedy and sorting5 min
- Merge a list of overlapping intervals, and justify the key you sorted byeasyAlso on sorting4 min
- Given a list of meetings with start and end times, tell me the minimum number of rooms needed to hold all of them.mediumAlso on sorting5 min