第一章：贪心算法之区间调度问题

labuladong贪心算法之区间调度问题

435. 无重叠区间

一天有好多活动，你可以选择不重叠的时间尽量多参加活动。

• 按照活动结束的时间排序后（不管开始得多早，都不如选择早点结束的活动，这样还能继续选其他活动）
  • 假设当前参加的是活动A，如果活动B的开始时间大于等于活动A的结束时间，则继续参加B活动。
  • 这时活动数+1，后面的活动开始时间要和活动B结束的时间进行比较，所以活动结束的时间更新为活动B结束的时间。

class Solution(object):
    def eraseOverlapIntervals(self, intervals):
        if not intervals: return 0
        intervals=sorted(intervals,key=lambda x : x[1])

        end=intervals[0][1]# 第0个活动结束的时间
        count=1
        for i in range(1,len(intervals)):
            # 可以想象成当前活动开始的时间大于等于之前活动结束的时间，那么参加当前活动
            if intervals[i][0]>=end:
                count+=1
                end=intervals[i][1]
        return len(intervals)-count

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