How many must you drop

Given a list of intervals, return the smallest number you must remove so that none of the ones left overlap.

Intervals that only touch, such as [1,2] and [2,3], do not count as overlapping here.

Worked example#

For [1,2] [2,3] [3,4] [1,3], sort by end:

[1,2] [1,3] [2,3] [3,4]

Now walk once, keeping an interval whenever it starts at or after the last one you kept:

One dropped, so the answer is 1.

Why sort by end and not by start#

Always keep the interval that finishes earliest, because finishing early leaves the most room for everything after it.

Sorting by start gives the wrong answer. Consider [1,100] [2,3] [4,5]. By start, [1,100] comes first, and keeping it forces you to drop both of the others, for an answer of 2. The right answer is 1: drop [1,100] and keep the two short ones.

That is the exchange argument in concrete form. Whatever the best possible selection is, swapping its first interval for the earliest-finishing one never makes it worse, so taking the earliest finisher is always safe.

Counting removals rather than keeps#

It is easier to count how many you keep and subtract. The two are the same question, and keeping is the one the greedy rule is stated in.

The cost#

Time O(n log n) for the sort, then one pass. Memory O(1) beyond the sort.

Constraints#

• 1 <= number of intervals <= 100000
• -50000 <= start < end <= 50000