Non-overlapping Intervals

Why it belongs on this sheet

This is a very good greedy problem because the optimal rule is not immediately obvious until you think in terms of future flexibility.

Pattern

Keep the interval with the smaller end

Approach

Sort by start. If the current interval overlaps the previous kept one, remove one interval and keep the one with the smaller ending time because it leaves more room for later intervals.

Java solution

import java.util.Arrays;

class Solution {
  public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    int removals = 0;
    int previousEnd = intervals[0][1];

    for (int i = 1; i < intervals.length; i++) {
      if (intervals[i][0] < previousEnd) {
        removals++;
        previousEnd = Math.min(previousEnd, intervals[i][1]);
      } else {
        previousEnd = intervals[i][1];
      }
    }

    return removals;
  }
}

Complexity

• Time: O(n log n)
• Space: O(1) extra apart from sorting

Interview note

The greedy choice is "keep the interval that ends earlier." That sentence is the proof sketch.