Non-overlapping Intervals

Problem

You are given a list of half-open intervals intervals, where intervals[i] = [start, end) covers the points start <= x < end. Two intervals that only touch ([1,2) and [2,3)) do not overlap. Return the minimum number of intervals you must remove so that the remaining intervals are pairwise non-overlapping.

• Up to around a hundred thousand intervals.
• Endpoints can be negative but fit comfortably in a normal int, with start < end.

Examples

• [[2,3],[3,4],[4,5],[2,4]] → 1. Removing [2,4] leaves three touching, non-overlapping intervals.
• [[3,4],[3,4],[3,4]] → 2. Identical intervals all overlap each other; only one can stay.
• [[3,4],[4,5]] → 0. Touching is allowed.

Hints

1. Removing the fewest intervals is the same as keeping the most. Which interval should you keep first if you want to leave the most room for the others?
2. Consider two overlapping intervals where one ends earlier. Is there ever a reason to keep the one that ends later instead?
3. Sort by end time; greedily keep each interval whose start is at least the end of the last kept one. The answer is n - kept.