easyCodingEntryMidSenior
Merge a list of overlapping intervals, and justify the key you sorted by
4 min readUpdated 2026-08-15
Answer
Short answer
Sorting by start time is what reduces the merge to a single scan carrying one scalar, the end of the open block; sorting by end breaks it, and sorting by end is instead correct for maximum non-overlapping selection.
Was this answer helpful?
Likely follow-ups
- How would you insert a single new interval into an already-merged list without re-sorting?
- The input arrives as a stream too large to sort. What changes?
- Given employee calendars, find the free slots common to all of them. What is the cost?
- Why does maximum non-overlapping selection sort by end time when merging sorts by start?
Related questions
- 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 intervals and sweep-line5 min
- Given everyone's busy calendar, find the slots when all of them are free. What do you sort, and what breaks at the boundaries?mediumAlso on intervals and sweep-line5 min
- Implement a FIFO queue using only two stacks, then tell me what a dequeue costs.mediumAlso on invariants4 min
- Given a list of meetings with start and end times, pick the largest set of them that do not overlap.mediumAlso on sorting4 min