Sorting by end, and why that is the greedy choice

Keeping the interval that frees you up soonest is provably optimal, and the proof is worth knowing.

A different question needs a different key

Everything so far sorted by start, because the questions were about what connects to what. Now the question changes: given conflicting intervals, keep as many as possible without any two overlapping.

Sorting by start is actively bad here. A single very long interval that starts first would be kept and would block everything after it.

Why it works

Sort by end, keep greedily

Process intervals in order of increasing end. Keep an interval whenever it starts at or after the last kept interval's end.

The reason is an exchange argument, and it is short enough to give out loud. Suppose some optimal selection exists. Look at the interval in it that finishes earliest, and compare it to the one this algorithm picked first, which finishes no later. Swapping the optimal one for the algorithm's leaves the rest of the selection valid, because the replacement frees the resource at least as early. So there is an optimal selection containing the algorithm's first pick, and the argument repeats on what remains.

That is what makes it provably optimal rather than a heuristic that passes the samples.

The whole difference is which end you sort on, so here is the same set of intervals under both keys.

1intervals = [[1, 100], [2, 3], [4, 5]]2 3print("by start:", sorted(intervals))4print("by end:  ", sorted(intervals, key=lambda pair: pair[1]))

Sorting by start puts the interval that blocks everything at the front. Sorting by end puts it last.

Complexity· 5 min

Cost of the greedy selection

The greedy selection is a sort followed by one pass that does constant work per interval. Give its time and space on n intervals, not counting the input itself.

Python

1for start, end in sorted(intervals, key=lambda pair: pair[1]):2    ...                        # constant work, and two scalars carried

Problem· 22 min

Non Overlapping Intervals

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

CodeGround