贪心算法解决区间重叠问题：最少移除区间数

在解决区间调度问题时，贪心算法是一种高效且直观的方法。下面笔者将详细介绍如何利用贪心算法解决“移除最少数量的区间以使剩余区间互不重叠”的问题，并逐步解析其技术实现细节。

问题描述

给定一个二维数组 intervals，每个子数组表示一个区间的起始和结束点（例如 [start, end]）。要求移除最少数量的区间，使得剩余区间互不重叠（起止相连不算重叠）。最终返回需要移除的区间数量。

示例输入输出：
输入：[[1,2], [2,4], [1,3]]
输出：1（移除 [1,3]）

算法思路

1. 问题分析
目标：最大化保留的区间数量 → 最小化移除的区间数量。
关键观察：选择结束时间最早的区间可以为后续区间留出更多空间，减少重叠可能。

 2. 贪心策略
1. 排序：按区间结束时间升序排列。
2. 遍历选择：
   保留第一个区间。
   从第二个区间开始，若当前区间与上一个保留的区间不重叠，则保留；否则移除。

3. 正确性证明
- 贪心选择性：每次选择结束最早的区间，确保局部最优。
- 最优子结构：剩余问题的最优解包含当前选择的最优解。

技术实现详解

1. 排序：按结束时间升序

sort(intervals.begin(), intervals.end(), 
     [](vector<int>& a, vector<int>& b) { 
         return a[1] < b[1]; 
     });

- Lambda表达式：自定义比较规则，按 `end` 升序排序。
- 时间复杂度：O(n log n)。

2. 初始化变量

int removed = 0;
int prev_end = intervals[0][1]; // 第一个区间的结束时间

3. 遍历并检查重叠
 

for (int i = 1; i < intervals.size(); ++i) {
    if (intervals[i][0] < prev_end) {
        removed++; // 重叠，移除当前区间
    } else {
        prev_end = intervals[i][1]; // 无重叠，保留并更新结束时间
    }
}

- 重叠判定：当前区间的起始 < 上一个区间的结束。
- 时间复杂度：O(n)。

完整代码

#include<iostream>
#include <vector>    // 支持 vector 容器
#include <algorithm> // 支持 sort 函数
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(),intervals.end(),[](vector<int>&a,vector<int>&b){return a[1]<b[1];});
    int n = intervals.size();
    int removedNum = 0;
    int prev_end = intervals[0][1];
    for(int i=1;i<n;i++)//遍历区间数组的起始值
    {
        if(intervals[i][0]<prev_end){//前一个区间的结束（prevend的最初值）大于后一个区间的起始值 就会重叠
        removedNum ++;
    }
    else{
        prev_end = intervals[i][1];
    }
       
    }
    return removedNum;
};
};

 关键点解析

1. 排序的作用
- 结束时间早优先：确保每次选择的区间对后续影响最小。
- 反例分析：若按开始时间排序，可能导致选择长时间区间，排除更多短区间。

2. 重叠判定逻辑
- 严格小于：intervals[i][0] < prev_end 表示有重叠。
- 起止相连不算重叠：若 `intervals[i][0] == prev_end，则不视为重叠。

3. 边界条件处理
- 空输入：直接返回0。
- 单区间：无需移除，返回0。

复杂度分析
- 时间复杂度：O(n log n)，主要由排序操作决定。
- 空间复杂度：O(1)（不考虑排序的栈空间）。

总结
核心：遍历思想+二维数组+Lambda表达式通过贪心算法按结束时间排序，能够高效解决区间重叠问题。该方法确保每次选择对后续影响最小的区间，从而全局最优。理解排序策略和重叠判定是掌握该算法的关键。

参考文献：LeetCode101 ——A Grinding guide