[leetcode] day104 no overlapping interval

subject

435. No overlap 【 secondary 】

Answer key

Dynamic programming

Dynamic planning old friend ！ Still don't know how to do ah hahaha

Algorithm :
First of all n The intervals are divided into left end points （ Or right endpoint ） Sort from small to large , Then the dynamic programming method is used to calculate the maximum number of intervals .

1. State definition ：dp[i] Indicates interval i For the last interval , The maximum number of non overlapping intervals that can be selected
2. State transition equation ：dp[i] = max(dp[j])+1,j<i, The first j The first interval must be the same as the i The intervals do not overlap .
3. Initial conditions ：dp[i]=1, The minimum number of removed intervals defaults to 1
4. Return value ：n-max(dp[i]), The rest is the minimum number of intervals to be removed

class Solution {
    
    public int eraseOverlapIntervals(int[][] intervals) {
    
        int n=intervals.length;
        Arrays.sort(intervals,new Comparator<int[]>(){
    
            public int compare(int[] intervals1,int[] intervals2){
    
                return intervals1[0]-intervals2[0];
            }
        });
        int[] dp=new int[n];
        Arrays.fill(dp,1);
        for(int i=1;i<n;i++){
    
        	// Traverse the previous interval 
            for(int j=0;j<i;j++){
    
                // No overlap 
                if(intervals[j][1]<=intervals[i][0])
                    dp[i]=Math.max(dp[i],dp[j]+1);
            }
        }
        return n-Arrays.stream(dp).max().getAsInt();
    }
}

Time complexity ：$O(n^2)$

Spatial complexity ：$O(n)$

What's wrong is , This problem of dynamic planning cannot pass , Will timeout … I thought I wrote something wrong , As a result, the official settlement also expired …

greedy

About why it is sorted by the right end of the interval ？
Sort by right endpoint , We must be able to find one End first Conference , Allow more time for later meetings , Here's the picture , choose a You can only ad, But if you choose b If you like, you can bcd, Remove an interval .

|_________|                   Section a
  |___|                       Section b       
       |__|                   Section c   
            |______|          Section d   

Then the question is Greedy strategy Namely , Sort intervals by right endpoint , If the currently traversed interval $[l_i,r_i]$ Does not coincide with the previous interval , namely $l_i\ge right$, Then we can greedily choose this range , And will right Updated to $r_i$

This inscription is easy to understand by drawing an interval diagram

class Solution {
    
    public int eraseOverlapIntervals(int[][] intervals) {
    
        int n=intervals.length;
        // The intervals are sorted by the right endpoint 
        Arrays.sort(intervals,new Comparator<int[]>(){
    
            public int compare(int[] intervals1,int[] intervals2){
    
                return intervals1[1]-intervals2[1];
            }
        });
        int res=1;// The remaining non overlapping intervals 
        int right=intervals[0][1];// Current rightmost endpoint position 
        for(int i=1;i<n;i++){
    
        	// The intervals do not overlap 
            if(intervals[i][0]>=right){
    
                res++;
                right=intervals[i][1];// Update the rightmost endpoint position 
            }
        }
        return n-res;
    }
}

Time complexity ：$O(nlogn)$

Spatial complexity ：$O(logn)$

↑ Are the complexity required for sorting