LeetCode 435 无重叠区间 HERODING的LeetCode之路-白红宇

LeetCode 435 无重叠区间 HERODING的LeetCode之路

阅读量：167 次

发布时间：2019-02-28

本文共 1133 字，大约阅读时间需要 3 分钟。

为了解决这个问题，我们需要找到最小的移除数量，使得剩下的区间互不重叠。我们可以使用贪心算法来解决这个问题，具体步骤如下：

方法思路

排序区间：首先将所有区间按照右端点从小到大排序。这样可以确保我们总是优先考虑右端点较小的区间，这样有助于减少后续区间的重叠可能性。

遍历区间：从左到右遍历这些排序后的区间。对于每个区间，如果它的左端点不小于当前记录的右端点，则保留这个区间，并更新当前记录的右端点。否则，该区间与已保留的区间重叠，需要移除。

计算移除数量：最后，移除的数量等于总区间数减去保留的区间数。

这种方法的时间复杂度主要是排序的时间复杂度 O(n log n)，其中 n 是区间的数量。遍历的时间复杂度是 O(n)，因此整体复杂度为 O(n log n)，能够高效地处理问题。

解决代码

#include 
   
    #include 
    
     using namespace std;int eraseOverlapIntervals(vector
     
      
       >& intervals) {    if (intervals.empty()) return 0;    sort(intervals.begin(), intervals.end(), [](const vector
       
        & a, const vector
        
         & b) { return a[1] < b[1]; }); int n = intervals.size(); int right = -1; int count = 0; for (const auto& interval : intervals) { if (interval[0] >= right) { right = interval[1]; count++; } } return n - count;}

代码解释

排序区间：使用 sort 函数对区间列表进行排序，排序依据是区间的右端点。

初始化变量：right 用于记录当前保留的区间的右端点，初始化为 -1。count 用于记录保留的区间数量，初始化为 0。

遍历区间：对于每个区间，检查其左端点是否大于等于 right。如果是，说明该区间不与已保留的区间重叠，可以保留，并更新 right 为该区间的右端点，同时增加 count。

计算结果：最后，返回移除的区间数量，计算方式为总区间数减去保留的区间数量。

这种方法确保了我们以最优的方式选择区间，移除尽可能少的区间，从而得到一个互不重叠的区间集合。

转载地址：http://cvkj.baihongyu.com/

你可能感兴趣的文章