435. Non-overlapping Intervals

经典题的变型。经典题讲的是给出一堆区间，选择最大不重叠的区间个数，而该题变型为求解最小移走的区间个数，本质就是一样的。 先对end排序，选择end最小的区间，然后移走所有重叠的区间。然后在剩下的区间中再选择end最小的区间，重复上述操作。

/** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */ class Solution { public: static bool cmp(Interval&a,Interval&b) { if(a.end<b.end) return true; else return false; } int eraSEOverlapIntervals(vector<Interval>& intervals) { if(intervals.size()<=1) return 0; sort(intervals.begin(),intervals.end(),cmp); int count=1; int nowIndex=0; int nextIndex=1; while(nextIndex<intervals.size()) { if(intervals[nowIndex].end>intervals[nextIndex].start) nextIndex++; else { count++; nowIndex=nextIndex; nextIndex++; } } return intervals.size()-count; } };