LeetCode 435 Non-overlapping Intervals - Greedy(Med, Java, O(nlogn))

Problem Statement

• LeetCode 435. 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.

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 <= 10^5
• intervals[i].length == 2
• -5 * 10^4 <= starti < endi <= 5 * 10^4

---

Solution Explanation

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        // Sort by end time
        int n = intervals.length;
        Arrays.sort(intervals, (a,b) -> Integer.compare(a[1],b[1]));

        int prev = 0;
        int count = 1;

        for (int i=1; i<n; i++) {
            if (intervals[i][0] >= intervals[prev][1]) {
                // if starts after previous end
                prev = i;
                count ++;
            }
        }

        return n - count;  // Missing return statement
    }
}

Algorithm Approach

Strategy: Find the maximum number of non-overlapping intervals, then subtract from total.

Key Insight: Two intervals [a,b] and [c,d] are non-overlapping if b <= c or d <= a.

Steps:

1. Sort by end time - Greedy choice: always pick intervals ending earliest
2. Count non-overlapping intervals - Select intervals that don't overlap with previously selected ones
3. Return difference - Total intervals minus non-overlapping intervals

Why Sort by End Time?

Sorting by end time ensures we make the optimal greedy choice. When we pick an interval with the earliest end time, we leave the maximum amount of space for future intervals.

Time & Space Complexity

• Time: O(n log n) due to sorting
• Space: O(1) additional space

The greedy approach guarantees the optimal solution because selecting intervals that end earliest always maximizes the number of non-overlapping intervals we can keep.