leetcode 435. Non-overlapping Intervals 消除覆盖区间 + 区间排序 && 遍历

电玩女神 2022-06-04 08:58 160阅读 0赞

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:  
You may assume the interval’s end point is always bigger than its start point.  
Intervals like \[1,2\] and \[2,3\] have borders “touching” but they don’t overlap each other.  
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.

这道题题意很简单，就是消除重复区间，就是设置一个前驱区间，嗯嗯，做法很棒的，做法的核心是这样的，当遇到重复区间的时候，每当当前的end小于pre的end的时候，修改pre，

这一道题[leetcode 452. Minimum Number of Arrows to Burst Balloons 消除覆盖区间][leetcode 452. Minimum Number of Arrows to Burst Balloons] 的做法和本体一样，值得一起学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <cmath>
    
    using namespace std;
    
    
    /*
    struct Interval 
    {
         int start;
         int end;
         Interval() : start(0), end(0) {}
         Interval(int s, int e) : start(s), end(e) {}
    };
    */
    
    bool cmp(Interval a, Interval b)
    {
        if (a.start != b.start)
            return a.start < b.start;
        else
            return a.end < b.end;
    }
    
    class Solution 
    {
    public:
        int eraseOverlapIntervals(vector<Interval>& in) 
        {
            sort(in.begin(),in.end(),cmp);
            int count = 0 , pre = 0;
            for (int now = 1; now < in.size(); now++)
            {
                if (in[now].start < in[pre].end)
                {
                    count++;
                    if (in[now].end < in[pre].end)
                        pre = now;
                }
                else
                    pre = now;
            }
            return count;
        }
    };

[leetcode 452. Minimum Number of Arrows to Burst Balloons]: http://blog.csdn.net/JackZhang_123/article/details/78760672