Interval scheduling

Interval scheduling asks: given many intervals, choose the largest set that do not overlap. Examples: the most talks one person can attend, or the fewest meetings to cancel so the rest fit (Non-overlapping Intervals, which is n minus the maximum kept).

The greedy rule is: always pick the interval that ends earliest among those compatible with what you have picked. Sorting by start or by length does not work in general; sorting by end does.

When intervals have weights (for example profit per job) the greedy fails, and you need dynamic programming with binary search: weighted interval scheduling, O(n log n).

1. 1Sort intervals by end time.
2. 2Keep last_end, the end of the most recently chosen interval, starting at minus infinity.
3. 3For each interval in order: if its start >= last_end (half-open; use > for closed intervals that must not touch), choose it and set last_end to its end. Otherwise skip it.
4. 4The number chosen is the maximum. The number skipped is the minimum to remove.
5. 5Why it works (exchange argument): any optimal solution's first interval can be swapped for the earliest-ending interval without causing a conflict, because that one ends no later. Repeat for the rest, so greedy is never worse.
6. 6Minimum arrows to burst balloons is the same sweep with closed intervals: each arrow at the current end bursts every balloon that starts at or before it.

def erase_overlap_intervals(intervals):
    # keep as many non-overlapping intervals as possible,
    # return how many must be removed
    intervals = sorted(intervals, key=lambda x: x[1])  # by END time
    kept = 0
    last_end = float("-inf")
    for start, end in intervals:
        if start >= last_end:           # fits after the last kept one
            kept += 1
            last_end = end
    return len(intervals) - kept

print(erase_overlap_intervals([[1, 2], [2, 3], [3, 4], [1, 3]]))  # 1

Sorting by end and keeping every interval that starts at or after the last kept end gives the maximum number of non-overlapping intervals; the rest must be removed. Touching intervals like [1, 2] and [2, 3] are treated as compatible.

Cost: O(n log n) time for the sort, O(1) extra space for the sweep. Weighted version: O(n log n) time, O(n) space.