区间集合：高效解决无重叠区间问题【贪心、区间集合】

无重叠区间问题的深入解析与C++实现

题目理解

在无重叠区间问题中，我们被给定一个区间集合 intervals，其中每个区间以 [start, end] 的形式表示。我们的目标是确定最少需要移除多少个区间，以确保剩下的区间互不重叠。值得注意的是，当两个区间仅在一个点上接触时（例如 [1, 2] 和 [2, 3]），它们被视为不重叠。

题目链接：435. 无重叠区间 - 力扣（LeetCode）

思考过程

1. 排序区间

处理该问题的第一步是对所有的区间按结束时间进行排序。选择结束时间的原因在于，如果我们能够优先保留结束时间较早的区间，就可以为后续可能的区间留出更多的空间。这个策略的本质是利用贪心算法思想：在每一步都选择局部最优解，以期望最终达到全局最优解。

2. 遍历并判断重叠

在对区间进行排序后，我们需要维护一个变量 current_end，表示当前不重叠区间的结束时间。初始化时，current_end 设置为负无穷。在遍历排序后的区间时，我们会执行以下步骤：

• 对于每一个区间，检查其起始时间是否大于或等于 current_end。
  • 无重叠：如果条件满足，说明当前区间可以被保留，随后更新 current_end 为当前区间的结束时间。
  • 重叠：如果不满足条件，则表示存在重叠，此时我们需要增加移除计数器。为了尽量保留更多的区间，我们选择移除结束时间较晚的那个区间。

3. 统计移除次数

每当我们发现需要移除一个区间时，计数器 count 增加一。最终，遍历完所有区间后，count 的值即为需要移除的最小区间数量。

C++实现

以下是用C++实现的代码：

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;

        // 按结束时间排序
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });

        int count = 0;          // 需要移除的区间数量
        int current_end = intervals[0][1]; // 初始化为第一个区间的结束时间

        // 从第二个区间开始遍历
        for (int i = 1; i < intervals.size(); ++i) {
            // 如果当前区间的起始时间小于当前的结束时间，说明重叠了
            if (intervals[i][0] < current_end) {
                count++; // 需要移除一个区间
            } else {
                // 没有重叠，更新当前结束时间
                current_end = intervals[i][1];
            }
        }

        return count;
    }
};

示例解释

1. 示例 1：

   • 输入: [[1,2],[2,3],[3,4],[1,3]]
   • 排序后的区间: [[1,2],[1,3],[2,3],[3,4]]
   • 遍历过程：
     • 保留 [1,2]，更新 current_end 为 2。
     • [1,3] 的起始时间 1 小于 current_end 2，计数加一。
     • 保留 [2,3]，更新 current_end 为 3。
     • 保留 [3,4]，更新 current_end 为 4。
   • 输出: 1（移除 [1,3]）

2. 示例 2：

   • 输入: [[1,2], [1,2], [1,2]]
   • 排序后不变，所有区间相同。
   • 遍历过程：
     • 保留第一个 [1,2]，更新 current_end。
     • 后面的两个 [1,2] 都重叠，计数加二。
   • 输出: 2（移除两个 [1,2]）

3. 示例 3：

   • 输入: [[1,2], [2,3]]
   • 排序后不变，两个区间不重叠。
   • 遍历过程：
     • 保留第一个 [1,2]，更新 current_end。
     • [2,3] 的起始时间 2 不小于 current_end，继续。
   • 输出: 0（不需要移除任何区间）

复杂度分析

• 时间复杂度：O(n log n)，主要来自于对区间的排序。排序的时间复杂度是 O(n log n)，遍历的时间复杂度是 O(n)，整体以排序为主。
• 空间复杂度：O(1)，只使用了常数额外空间来存储变量。排序过程中会使用 O(n) 的空间，但在这里我们只考虑算法本身使用的额外空间。

代码的可扩展性

虽然当前实现已经能有效解决问题，但我们可以考虑以下几种扩展：

1. 输入验证：可以增加对输入有效性的检查，比如判断区间的起始时间是否小于结束时间。
2. 支持多种数据结构：将函数修改为支持其他数据结构，例如链表或自定义的区间类，以提高灵活性。
3. 返回移除的区间：除了返回移除的数量，还可以修改代码，使其返回具体需要移除的区间，以便于用户了解具体情况。

总结

通过对区间的排序和遍历，我们能够高效地解决无重叠区间的问题。利用贪心算法的策略，保持当前的结束时间来判断是否重叠，使得我们的解决方案简单而有效。这种方法适用于大规模输入，能够在合理的时间内得出结果。希望这篇解析能帮助读者更好地理解和实现无重叠区间的问题，提升编程和算法思维能力。