LeetCode题解——贪心算法（二）

忘是亡心i 2023-06-06 07:49 2阅读 0赞

### 文章目录 ###

*  435. 无重叠区间
 *   *   *  按起点排序的贪心算法
         *   *  统计移除区间数
             *  统计保留区间数
         *  按区间终点排序的贪心算法
         *   *  统计保留区间数
             *  统计移除区间数

对于刷题，我的看法是刷题不在多而在精，弄懂每一类具有代表性的题目，就可以达到举一反三、事半功倍的效果。还要多总结、多思考。

# 435. 无重叠区间 #

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

可以认为区间的终点总是大于它的起点。  
区间 \[1,2\] 和 \[2,3\] 的边界相互“接触”，但没有相互重叠。

示例 1:

输入: [ [1,2], [2,3], [3,4], [1,3] ]
    
    输出: 1
    
    解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: [ [1,2], [1,2], [1,2] ]
    
    输出: 2
    
    解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: [ [1,2], [2,3] ]
    
    输出: 0
    
    解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

### 按起点排序的贪心算法 ###

对每个区间根据起始点大小升序，如果区间没有重叠则都保留；如果区间有重叠，则保留区间终点小的那个区间，这样可以保留更多的区间，达到总移除区间数最小的目的。  
![format_png][]  
![format_png 1][]

#### 统计移除区间数 ####

bool cmp(const vector<int> &a, const vector<int> &b)
    {
        
        return a[0] < b[0];
    }
    class Solution {
        
    public:
        int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        
            if(intervals.size() == 0)
                return 0;
            int ans = 0;
            int curpos = 0;
            sort(intervals.begin(), intervals.end(), cmp);
            for(int i = 1; i < intervals.size(); ++i)
            {
        
                if(intervals[curpos][1] > intervals[i][0])
                {
        
                    if(intervals[curpos][1] > intervals[i][1])
                    {
        
                        curpos = i;
                    }
                    ans++;
                }
                else
                {
        
                    curpos = i; // 不移除，更新当前区间
                }
            }
            return ans;
        }
    };

时间复杂度：O(nlog(n))。排序需要O(nlog(n)) 的时间。

空间复杂度：O(1)。不需要额外空间。

#### 统计保留区间数 ####

bool cmp(const vector<int> &a, const vector<int> &b)
    {
        
        return a[0] < b[0];
    }
    class Solution {
        
    public:
        int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        
            if(intervals.size() == 0)
                return 0;
            int ans = 1; // 统计当前不移除区间数
            int curpos = 0;
            sort(intervals.begin(), intervals.end(), cmp);
            for(int i = 1; i < intervals.size(); ++i)
            {
        
                if(intervals[curpos][1] > intervals[i][0])
                {
        
                    if(intervals[curpos][1] > intervals[i][1])
                    {
        
                        curpos = i;
                    }
                }
                else
                {
        
                    ans++;
                    curpos = i; // 不移除，更新当前区间
                }
            }
            return intervals.size() - ans;
        }
    };

时间复杂度：O(nlog(n))。排序需要O(nlog(n)) 的时间。

空间复杂度：O(1)。不需要额外空间。

### 按区间终点排序的贪心算法 ###

![format_png 2][]  
![format_png 3][]

#### 统计保留区间数 ####

排序后，当前区间的终点小于等于下一区间的起点的区间都保留。

bool cmp(const vector<int> &a, const vector<int> &b)
    {
        
        return a[1] < b[1];
    }
    class Solution {
        
    public:
        int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        
            if(intervals.size() == 0)
                return 0;
            int ans = 1; //统计保留区间数
            int curpos = 0;
            sort(intervals.begin(), intervals.end(), cmp);
            for(int i = 1; i < intervals.size(); ++i)
            {
        
                if(intervals[curpos][1] <= intervals[i][0])
                {
        
                    curpos = i;
                    ans++;
                }
            }
            return intervals.size() - ans;
        }
    };

时间复杂度：O(nlog(n))。排序需要O(nlog(n)) 的时间。

空间复杂度：O(1)。不需要额外空间。

#### 统计移除区间数 ####

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

时间复杂度：O(nlog(n))。排序需要O(nlog(n)) 的时间。

空间复杂度：O(1)。不需要额外空间。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhcmRzZXB0ZW1iZXI_size_16_color_FFFFFF_t_70]

[format_png]: /images/20230601/6c0a351df10b45cd9ece2a47556cf590.png
[format_png 1]: /images/20230601/f7cacd7aca5942e4a29c2603dcba9986.png
[format_png 2]: /images/20230601/5a729a5744374a699e2ea9b3d86fa4bf.png
[format_png 3]: /images/20230601/8afcf94e8cff4b17ad2185d75f25f611.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhcmRzZXB0ZW1iZXI_size_16_color_FFFFFF_t_70]: /images/20230601/709072323c41450894565555cd96c4c1.png