Non-overlapping Intervals

Remove the fewest intervals so the rest never overlap: sort by end and greedily keep every interval that starts after the last kept one ends.

The idea

Keeping the most intervals is the same as removing the fewest. Among all intervals, the one that ends first leaves the most room for everything after it, so keep it. Then skip everything that clashes with it and repeat with the next interval that starts at or after its end. Sorting by end makes that a single left-to-right scan with one variable: the end of the last kept interval.

Code

public static int EraseOverlapIntervals(int[][] intervals) {
    Array.Sort(intervals, (x, y) => x[1].CompareTo(y[1]));
    int removed = 0, end = int.MinValue;
    foreach (var iv in intervals) {
        if (iv[0] >= end) {
            end = iv[1]; // keep it: it starts after the last kept one ends
        } else {
            removed++; // it clashes with the last kept interval
        }
    }
    return removed;
}

Tips

• Sort by END, not by start: sorting by start would keep a long early interval like [1, 7] that blocks many short ones.
• Touching intervals such as [1, 3] and [3, 5] do not overlap here, so the test is start >= end, not start > end.
• The same greedy counts the maximum set of non-overlapping intervals (activity selection); the answer is n minus that count.

In the .NET library

Array.Sort with a Comparison<int[]> sorts the jagged array in place. Use x[1].CompareTo(y[1]) rather than x[1] - y[1]: subtraction can overflow when values are near int.MinValue or int.MaxValue.