1、问题描述

给定一组区间，要求移除最少数量的区间，使得剩下的区间互不重叠。区间只在端点接触不算重叠。

2、解题思路

这是一个典型的区间调度问题，可以使用贪心算法解决：

1. 按照区间结束时间排序
2. 选择结束时间最早的区间
3. 移除所有与该区间重叠的区间
4. 重复上述过程直到处理完所有区间

3、实现代码

#include <stdlib.h>

// 比较函数，用于区间排序（按结束时间升序）
int compare(const void* a, const void* b) {
    int* intervalA = *(int**)a;
    int* intervalB = *(int**)b;
    return intervalA[1] - intervalB[1]; // 按结束时间排序
}

int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize) {
    if (intervalsSize == 0) return 0;
    
    // 1. 按照区间结束时间排序
    qsort(intervals, intervalsSize, sizeof(int*), compare);
    
    int count = 0;          // 需要移除的区间数量
    int prevEnd = intervals[0][1]; // 前一个选中区间的结束时间
    
    // 2. 遍历所有区间
    for (int i = 1; i < intervalsSize; i++) {
        // 当前区间的开始时间 < 前一个区间的结束时间 → 有重叠
        if (intervals[i][0] < prevEnd) {
            count++; // 需要移除当前区间
        } else {
            // 无重叠，更新前一个区间的结束时间
            prevEnd = intervals[i][1];
        }
    }
    
    return count;
}

4、代码解析

1. 排序函数：

   • compare函数按区间结束时间升序排序
   • 使用qsort对区间数组进行排序

2. 贪心选择：

   • 初始化prevEnd为第一个区间的结束时间
   • 遍历后续区间，如果当前区间开始时间小于prevEnd，说明有重叠，需要移除
   • 否则更新prevEnd为当前区间的结束时间

3. 边界处理：

   • 空数组直接返回0
   • 单元素数组也返回0（无需移除）

5、复杂度分析

• 时间复杂度：O(n log n)，主要是排序的时间
• 空间复杂度：O(1)，只使用了常数空间

6、示例验证

输入：[[1,2],[2,3],[3,4],[1,3]]

1. 排序后：[[1,2],[2,3],[1,3],[3,4]]
2. 选择[1,2]，跳过[2,3]，移除[1,3]，选择[3,4]
3. 输出：1

输入：[[1,2],[1,2],[1,2]]

1. 排序后：[[1,2],[1,2],[1,2]]
2. 选择第一个[1,2]，移除后两个[1,2]
3. 输出：2

输入：[[1,2],[2,3]]

1. 排序后：[[1,2],[2,3]]
2. 选择[1,2]，[2,3]不重叠
3. 输出：0

7、关键点总结

1. 排序策略：按结束时间排序能最大化剩余区间数量
2. 贪心选择：每次选择结束时间最早的区间
3. 重叠判断：当前开始时间 < 前一个结束时间即为重叠
4. 边界处理：正确处理空数组和单元素数组

8、常见问题解答

Q: 为什么按结束时间排序？
A: 这样能保证每次选择的区间对后续选择影响最小，最大化剩余区间数量。

Q: 如何处理端点接触的情况？
A: 题目说明端点接触不算重叠，所以判断条件是严格小于。

Q: 这个算法能处理所有情况吗？
A: 是的，这个贪心算法能保证找到最优解。

Q: 为什么时间复杂度是O(n log n)？
A: 主要时间消耗在排序上，后续遍历是O(n)。

转载自CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/qq_41840843/article/details/149419247