Non-overlapping Intervals

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]] Output: 1 Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Example 2:

Input: intervals = [[1,2],[1,2],[1,2]] Output: 2 Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:

Input: intervals = [[1,2],[2,3]] Output: 0 Explanation: You don’t need to remove any of the intervals since they’re already non-overlapping.

Constraints:

• 1 <= intervals.length <= 105
• intervals[i].length == 2
• -5 * 104 <= starti < endi <= 5 * 104

Approach: Greedy with Sorting by End Time (Interval Scheduling)

Algorithm

1. Sort the intervals by their ending time
2. Keep track of the end time of the last kept interval
3. Iterate through intervals: if the current interval starts at or after the last kept end, keep it and update the end; otherwise remove it and increment the removal counter
4. Return the number of removed intervals

Time & Space Complexity

• Time Complexity: O(n log n) - dominated by sorting
• Space Complexity: O(n) - space used by the sorting algorithm (Java’s Arrays.sort on objects)

Java Implementation

import java.util.Arrays;

public class NonOverlappingIntervals {

    /**
     * Return the minimum number of intervals to remove.
     * @param intervals Array of [start, end] intervals
     * @return Number of intervals to remove
     */
    public static int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

        int removals = 0;
        int lastEnd = Integer.MIN_VALUE;

        for (int[] interval : intervals) {
            if (interval[0] >= lastEnd) {
                // Non-overlapping (touching is allowed), keep it
                lastEnd = interval[1];
            } else {
                // Overlapping, remove it
                removals++;
            }
        }

        return removals;
    }

    // Test method
    public static void main(String[] args) {
        int[][] intervals1 = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};
        System.out.println("Input: intervals = [[1,2],[2,3],[3,4],[1,3]]");
        System.out.println("Output: " + eraseOverlapIntervals(intervals1)); // Expected: 1

        int[][] intervals2 = {{1, 2}, {1, 2}, {1, 2}};
        System.out.println("Input: intervals = [[1,2],[1,2],[1,2]]");
        System.out.println("Output: " + eraseOverlapIntervals(intervals2)); // Expected: 2

        int[][] intervals3 = {{1, 2}, {2, 3}};
        System.out.println("Input: intervals = [[1,2],[2,3]]");
        System.out.println("Output: " + eraseOverlapIntervals(intervals3)); // Expected: 0
    }
}

Example Walkthrough

For intervals = [[1,2],[2,3],[3,4],[1,3]]:

1. Sort by end: [[1,2],[2,3],[1,3],[3,4]]
2. i=0 [1,2]: start 1 >= MIN, keep. lastEnd=2
3. i=1 [2,3]: start 2 >= 2, keep. lastEnd=3
4. i=2 [1,3]: start 1 < 3, overlapping, remove. removals=1
5. i=3 [3,4]: start 3 >= 3, keep. lastEnd=4

Answer: 1.

Key Points

1. Greedy Choice: Keep the interval that ends earliest to leave the most room for others
2. Touching Allowed: start >= lastEnd means the intervals are non-overlapping
3. Equivalent Problem: Minimize removals = total intervals - maximum non-overlapping subset
4. Overflow Safety: Use Integer.compare for the comparator
5. O(n log n): Sorting dominates the runtime