[435] Non-overlapping Intervals

 1 class Solution {
 2 public:
 3     int eraseOverlapIntervals(vector<vector<int>>& intervals) {
 4 
 5         if(intervals.size() == 0)
 6             return 0;
 7 
 8         sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){
 9             if(a[0] != b[0]) return a[0] < b[0];
10             return a[1] < b[1];
11         });
12 
13         vector<int> dp(intervals.size(), 1);
14         for(int i = 1 ; i < intervals.size() ; i ++)
15             for(int j = 0 ; j < i ; j ++)
16                 if(intervals[i][0] >= intervals[j][1])
17                     dp[i] = max(dp[i], 1 + dp[j]);
18 
19         return intervals.size() - dp.back();
20     }
21 };

 1 class Solution {
 2 
 3 public:
 4     int eraseOverlapIntervals(vector<vector<int>>& intervals){
 5 
 6         if(intervals.size() == 0)
 7             return 0;
 8 
 9         sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){
10             if(a[0] != b[0]) return a[0] < b[0];
11             return a[1] < b[1];
12         });
13 
14         int res = 1;
15         int pre = 0;
16         for(int i = 1 ; i < intervals.size() ; i ++)
17             if(intervals[i][0] >= intervals[pre][1]){
18                 pre = i;
19                 res ++;
20             }
21             else if(intervals[i][1] < intervals[pre][1])
22                 pre = i;
23 
24         return intervals.size() - res;
25     }
26 };