435. Non-overlapping Intervals ------M ~~！！！~~

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

 

Example 1:

Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Example 2:

Input: [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.

Example 3:

Input: [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

 

Note:

1. You may assume the interval's end point is always bigger than its start point.
2. Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.

A:

我首先想到的是，每次删除最多重复的interval,

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

class Solution { public: int eraseOverlapIntervals(vector<vector<int>>& intervals) { sort(intervals.begin(), intervals.end()); int n = intervals.size(); vector<vector<int>> overlaps(n, vector<int>()); for (int i = 0; i < n; i++) { auto& a = intervals[i]; for (int j = i + 1; j < n; j++) { auto& b = intervals[j]; if (b[0] >= a[1]) { break; } else { overlaps[i].push_back(j); overlaps[j].push_back(i); } } } int res = 0; while (true) { // go through to find the max overlap count int maxCount = 0; int maxIndex = -1; for (int i = 0; i < n; i++) { if (overlaps[i].size() > maxCount) { maxCount = overlaps[i].size(); maxIndex = i; } } if (maxIndex < 0) break; res++; // remove all that's overlap with maxIndex auto& tmp = overlaps[maxIndex]; for (auto t : tmp) { auto& curInter = overlaps[t]; for (auto it = curInter.begin(); it != curInter.end(); it++) { if (*it == maxIndex) { curInter.erase(it); break; } } } overlaps[maxIndex].clear(); } return res; } };

然而，这个算法，对于这个例子是不对的。

[[0,2],[1,3],[1,3],[2,4],[3,5],[3,5],[4,6]]

*************换了个思考方式。 转而寻找最长的不相交区间****************

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

class Solution { public: int eraseOverlapIntervals(vector<vector<int>>& intervals) { int n = intervals.size(); if( n <= 1){ return 0; } // think from the other side, we actually need to find the longest non-overlap intervals auto compare = [](const vector<int>& a, const vector<int>& b){ if(a[1] == b[1]) return a[0] < b[0]; return a[1] < b[1]; //increasing order of end position }; sort(intervals.begin(), intervals.end(), compare); int nonOverlapCount = 1; // greedy search to find the first can finished interval int preIndex = 0; for(int i =1;i<n; i++){ if(intervals[i][0] >= intervals[preIndex][1]){ ++nonOverlapCount; preIndex = i; } } return intervals.size() - nonOverlapCount; } };