Non Overlapping Intervals

435. 无重叠区间

分析

要保证最多的不重叠区间数，可以采用如下贪心策略：
- 按区间的结束点升序排序：结束点越早，剩余空间越多，更容易为后续区间预留空间
- 遍历排序后的区间，选择与前一个区间不重叠的区间，将其加入到保留的集合中

先按结束点排序。
初始化计数变量 count，记录当前不wq重叠区间的数量，初始值为 1
遍历排序后的区间：
- 如果当前区间的起始点 start 不小于上一个保留区间的结束点 cur，说明它与前面的区间不重叠，更新 cur 并增加计数
最后，用总区间数减去 count 即为需要移除的区间数

时间复杂度

排序的时间复杂度为 O(nlogn) ，其中 n 是区间的数量
遍历区间的复杂度为 O(n)

总时间复杂度为 O(nlogn)

空间复杂度

空间复杂度为 O(1)

C++代码

 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


class Solution
{
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals)
    {
        // 如果没有区间，直接返回 0
        if (intervals.empty())
            return 0;

        // 按区间的结束点升序排序
        std::sort(intervals.begin(), intervals.end(), [](std::vector<int> a, std::vector<int> b) {
            return a[1] < b[1];
        });

        // 初始化计数器和当前区间结束点
        int count = 1; // 至少有一个区间不重叠
        int cur = intervals[0][1];

        // 遍历剩余的区间
        for (int i = 1; i < intervals.size(); ++i)
        {
            // 如果当前区间不重叠，则更新结束点并增加计数
            if (cur <= intervals[i][0])
            {
                ++count;
                cur = intervals[i][1];
            }
        }

        // 总区间数 - 不重叠区间数 = 需要移除的区间数
        return intervals.size() - count;
    }
};