[interval problem] 435 Non overlapping interval

One 、 subject

Given a set of intervals , Find the minimum number of intervals to remove , Keep the remaining intervals from overlapping .

Be careful :

It can be said that the end of an interval is always greater than its starting point .
Section [1,2] and [2,3] The boundaries of each other “ Contact ”, But there is no overlap .
Example 1:

Input : [ [1,2], [2,3], [3,4], [1,3] ]

Output : 1

explain : remove [1,3] after , There's no overlap in the rest .
Example 2:

Input : [ [1,2], [1,2], [1,2] ]

Output : 2

explain : You need to remove two [1,2] So that the rest of the intervals don't overlap .
Example 3:

Input : [ [1,2], [2,3] ]

Output : 0

explain : You don't need to remove any intervals , Because they are already non overlapping .

Two 、 Answer key

This problem involves removing the minimum number of intervals , Analysis leads to , To make the last number of intervals reserved more , As long as the value at the end of each interval is small enough . therefore , The greedy strategy is to preferentially keep the disjoint intervals with small endings .

• First , Sort each interval according to the element at the end of the interval （ Ascending ）
• then , Compare the end element value of the interval with the start value to judge whether the interval intersects , Until the end of the comparison interval

The determination of the intersection of intervals in this question ：
Start from the end of the first interval , Compare with the starting element of the next interval , If the starting element of the next interval is less than prev1, Then it means that the next interval overlaps with it , discarded . In this way, it is compared with the starting element of the lower interval in turn , Until the starting element of the next interval is greater than prev1, Description no overlap , to update prev2 Is the end element of the interval , cycle .

3、 ... and 、 Code

class Solution {
    
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    
      if(intervals.empty()) return 0;
      int n = intervals.size();
      sort(intervals.begin(),intervals.end(),[](vector<int>&a,vector<int>&b){
    
         return a[1]<b[1]; 
      });
      int total = 0,prev = intervals[0][1];
      for(int i = 1;i<n;i++){
    
          if(intervals[i][0]<prev) total++;
          else prev = intervals[i][1];
      }
      return total;
    }
};