Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals 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.

Example 1:

1
2
3
4
5
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:

1
2
3
4
5
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:

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

思路

我们在使用C++ STL中的sort()函数时，如果vector中的元素是普通的int或者string，不需要额外撰写排序函数。sort()函数会自动将vector从小到大进行排列。如果vector里面的元素是自定义的struct/class，我们就需要重载排序函数。
利用贪心算法，将排序后的结果依次找寻局部最优即可。我们要注意在寻找的过程中，其中的一个边界条件。我们需要保证找到的元素，其范围是相对最小的。如[-100,-87], [-100, –32]……[-87, -20], [-86, -1], [-85, -72]……，很明显，当我们从[-100,-87]跳转到[-87, -20]时，我们取到的[-87, -20]是局部最优。但是当访问到[-85, -72]时，我们应该舍弃[-87, -20]，将最优元素计为[-85, -72]。因为其所涉及的范围比[-87, -20]小。

因此有

1
if ( (intervals[i+1].start - tmpstart) + (intervals[i+1].end - intervals[i+1].start) < region )

这个条件判断。

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
50
51
52
53
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
const bool less_start(const Interval &m1, const Interval &m2)
{
    if(m1.start != m2.start) return m1.start < m2.start;
    else return m1.end < m2.end;
}
class Solution {
public:
    int eraseOverlapIntervals(vector<Interval>& intervals) {
        int count = 0;
        int size = intervals.size();
        int tmpstart = 0;
        int tmpend = 0;
        int region = 0;
        sort(intervals.begin(), intervals.end(), less_start);
        if (size > 0){
            tmpend = intervals[0].end;
            tmpstart = intervals[0].start;
            region = tmpend - tmpstart;
        }
        else 
            return 0;
        for(int i = 0; i < intervals.size() - 1; i++){
            if (intervals[i].start == intervals[i+1].start)
                count++;
            else{
                if(intervals[i+1].start < tmpend){
                    if ( (intervals[i+1].start - tmpstart) + (intervals[i+1].end - intervals[i+1].start) < region ){
                        tmpend = intervals[i+1].end;
                        tmpstart = intervals[i+1].start;
                        region = tmpend - tmpstart;
                    }
                    count++;
                }
                else{
                    tmpend = intervals[i+1].end;
                    tmpstart = intervals[i+1].start;
                    region = tmpend - tmpstart;
                }
            }
        }
        return count;
    }
};