Non-overlapping Intervals

Intuition

Minimum removals = n - max non-overlapping intervals. Greedy: sort by end time. Keep intervals with earliest end that don't overlap.

Algorithm

1Sort by end time. Track last end.
2If start >= last_end: keep it, update last_end.
3Else: remove it (count removal).

Common Pitfalls

•Sort by END time for greedy. This maximizes kept intervals, minimizing removals.

Non-overlapping Intervals.java

Java

// Approach: Sort by end time. Greedily keep intervals; if overlap with previous, remove the one ending later.
// Time: O(n log n) Space: O(1)
class Solution {
    static int minRemoval(int arr[][]) {
        Arrays.sort(arr, (a, b) -> (a[1] - b[1]));
        int s = arr[0][0];
        int e = arr[0][1];
        int cnt = 0;
        for (int i = 1; i < arr.length; i++) {
            if (Math.max(s, arr[i][0]) < Math.min(e, arr[i][1]))
                cnt++;
            else {
                s = arr[i][0];
                e = arr[i][1];
            }
        }
        
        return cnt;
    }
}

Was this solution helpful?