Non-overlapping Intervals

Share

Given an array of intervals, find the minimum number of intervals to remove to make the rest non-overlapping.

Example 1
Input: [[1,2],[2,3],[3,4],[1,3]] → Output: 1
Example 2
Input: [[1,2],[1,2],[1,2]] → Output: 2

Solution Approach

Greedy: sort by end time. Keep the interval with the earliest end time; remove overlapping ones.

  • Sort by end time.
  • Greedily keep the first interval (earliest end). Count = 0.
  • For each next interval: if it starts >= previous end, keep it (update prevEnd).
  • Otherwise, remove it (count++).
Java
import java.util.*;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a,b) -> a[1] - b[1]);
        int prevEnd = intervals[0][1], remove = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < prevEnd) remove++;
            else prevEnd = intervals[i][1];
        }
        return remove;
    }
}
  • Time Complexity: O(N log N)
  • Space Complexity: O(1)