435. Non-overlapping Intervals!

Greedy For this, firstly we sort the given intervals based on the end points. Then, we traverse over the sorted intervals. While traversing, if there is no overlapping between the previous interval and the current interval, we need not remove any interval. But, if an overlap exists between the previous interval and the current interval, we always drop the current interval.

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        // greedy
        // For this, firstly we sort the given intervals based on the end points. Then, we traverse over the sorted intervals. While traversing, if there is no overlapping between the previous interval and the current interval, we need not remove any interval. But, if an overlap exists between the previous interval and the current interval, we always drop the current interval.
        int ans = 0;
        // sort the intervals based on the end of each interval
        Arrays.sort(intervals, (a,b)->a[1]-b[1]);
        int end = intervals[0][1];
        for (int i=1; i<intervals.length; i++){
            if(intervals[i][0]<end){
                ans++;
            }else{
                end=intervals[i][1];
            }
        }
        return ans;
    }
}

DP

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        //dp[i]: max number of intervals that can be included until i. 
        // (interval i must be included)
        //dp[0]=1;
        
        Arrays.sort(intervals, (a,b)->a[0]-b[0]);
        int len = intervals.length;
        int[] memo = new int[len];
        memo[0]=1;
        int maxValid = 1;
        for(int i = 1; i<len; i++){
            for(int j=i-1; j>=0; j--){ 
                memo[i] = Math.max(memo[i], intervals[j][1]>intervals[i][0]? 1 : memo[j]+1);
            }
            maxValid = memo[i]>maxValid ? memo[i] : maxValid;
        }
        
        return len - maxValid;
    }
}