Sort intervals by start or by end?

Greedy choices and intervals Junior Python 3.13+ Reviewed By Best Latest Apps

Pick the fix

You need the fewest points so that every interval contains at least one. Which sort?

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A By end, placing a point at the end of each interval not yet hit

Right: the end is the latest place that still hits this interval, so it hits the most later ones.

Choosing the end point is the same exchange argument as keeping the earliest-ending booking.

Why not the others?
  • B By start, placing a point at each start. That can place many more points than needed.
  • C By length, shortest first. Length ignores where intervals sit on the line.

30-second answer

Sort by start when you are combining or inserting: overlapping intervals become neighbours. Sort by end when you are choosing the most intervals that do not overlap: finishing earliest leaves the most room. For 'how many at once', sort start and end events together.

Practise saying it · 30 s. No recording, just a timer

Explain how to choose the interval sort.

Say your answer out loud, then check which of these points you covered:

  • Start: merge or insert
  • End: keep the most
  • Events: peak overlap

Deep dive

Merging, inserting, finding gaps: by start.

Most non-overlapping, fewest points to hit all, fewest removals: by end.

Peak overlap: events, or by start with a heap of ends.

Common mistakes

  • Sorting by start for 'keep the most', which picks long early intervals.
  • Sorting by end for merging, which can miss overlaps with long earlier intervals.

Senior take & follow-ups

Name the sort key and the reason in one sentence.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you find free time across several calendars?

    Show hint

    Merge all busy intervals by start, then report the gaps.

  2. What sort does 'fewest points to hit every interval' use?

    Show hint

    By end: place a point at each end that is not already hit.

What each operation costs: Merge Sort · Quick Sort

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.