3.24 Non-overlapping Intervals

3.24.1 Problem Metadata

3.24.2 Description

Given a collection of intervals, find the minimum number of intervals to remove so the rest are non-overlapping.

3.24.3 Examples

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

3.24.4 Constraints

  • 1 <= intervals.length <= 10^5
  • intervals[i].length == 2

3.24.5 Solution - Greedy by End Time

3.24.5.1 Walkthrough

Sort intervals by end time; keep a running end boundary for the last accepted interval. When an interval starts after or at the stored end, include it and update the end. Otherwise it overlaps and must be removed. The number removed equals total minus selected count.

3.24.5.2 Analysis

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

3.24.5.3 Implementation Steps

  1. Sort intervals ascending by end, breaking ties by start.
  2. Initialize count = 1, end = intervals[0][1].
  3. For each remaining interval:
    • If interval[0] >= end, increment count and set end = interval[1].
  4. Return n - count removals.

3.24.5.4 Code - Java

public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) {
        return 0;
    }

    Arrays.sort(intervals, (a, b) -> {
        if (a[1] != b[1]) {
            return a[1] - b[1];
        }
        return a[0] - b[0];
    });

    int count = 1;
    int end = intervals[0][1];

    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= end) {
            count++;
            end = intervals[i][1];
        }
    }

    return intervals.length - count;
}