Example: 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.

Solution

• Sort by end
• count number of non overlapping
• return total - count

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

        // Greedy Choice: By sorting the intervals by their end times, you ensure 
        // that you are always considering the interval that finishes the earliest first. 
        // This allows you to "free up" as much room as possible for subsequent intervals to fit without overlapping.
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

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

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