C++贪心算法：区间问题专题

"高效解决区间调度、覆盖与合并问题"

@鞠大龙
魅客科创中心

CONTENTS

目录

1. 贪心算法基础

1.1 贪心算法概念

  • 贪心算法定义：一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是全局最优的算法策略

  • 核心思想：通过局部最优选择，期望达到全局最优解

  • 适用条件：

    • 问题具有最优子结构：问题的最优解包含子问题的最优解
    • 具有贪心选择性质：局部最优选择可以导致全局最优解
    • 满足无后效性：之前的选择不会影响后面的选择

  • 与动态规划的区别：

    • 贪心算法：每步只考虑当前最优解，不回溯
    • 动态规划：考虑所有可能的解，通过递推关系求最优解
C++贪心算法 区间问题专题 2025年5月10日

1.2 贪心算法的优缺点

优点：

  • 时间复杂度通常较低
  • 实现简单直观
  • 空间复杂度通常为O(1)或O(n)
  • 适合解决某些特定类型的问题

缺点：

  • 不是所有问题都适用
  • 难以证明算法的正确性
  • 可能得到次优解而非最优解
  • 需要仔细设计贪心策略
// 贪心算法通用框架
void greedyAlgorithm(Problem problem) {
    Solution solution = {};  // 初始化空解
    
    while (!problem.isSolved()) {
        // 1. 选择当前最优选择
        Choice bestChoice = findBestChoice(problem);
        
        // 2. 将选择添加到解中
        solution.add(bestChoice);
        
        // 3. 更新问题状态
        problem.update(bestChoice);
    }
    
    return solution;
}
C++贪心算法 区间问题专题 2025年5月10日

1.3 贪心算法的证明方法

贪心算法正确性证明的常用方法

  1. 反证法：假设贪心算法不是最优的，然后推导出矛盾

  2. 交换论证：证明任何非贪心解都可以通过交换变成贪心解而不会变差

  3. 归纳法：证明每一步贪心选择都是最优的

  4. 数学归纳法：证明前k步贪心选择是最优的，然后证明第k+1步也是最优的

C++贪心算法 区间问题专题 2025年5月10日

2. 区间问题概述

2.1 区间问题的定义

  • 区间表示：通常用二元组 [start, end] 表示一个区间

  • 常见区间问题类型：

    • 区间调度：在不重叠的前提下选择最多的区间
    • 区间覆盖：用最少的区间覆盖一条线段
    • 区间合并：合并所有重叠的区间
    • 区间交集：求多个区间的交集

  • 应用场景：

    • 资源分配（会议室、CPU时间片）
    • 任务调度（作业调度、项目规划）
    • 网络带宽分配
    • 时间管理系统
C++贪心算法 区间问题专题 2025年5月10日

2.2 区间问题的贪心策略

常见贪心策略：

  1. 按结束时间排序

    • 适用于区间调度问题
    • 优先选择结束早的区间

  2. 按开始时间排序

    • 适用于某些区间合并问题
    • 按区间起点顺序处理

  3. 按区间长度排序

    • 适用于某些区间覆盖问题
    • 优先选择短区间或长区间

  4. 按特定指标排序

    • 如按区间权重/价值排序
    • 按区间与参考点的距离排序
// 区间结构定义
struct Interval {
    int start;
    int end;
    
    // 可选：其他属性
    int weight;  // 权重
    int id;      // 标识符
    
    // 按结束时间排序
    bool operator<(const Interval& other) const {
        return end < other.end;
    }
};

// 区间排序示例
void sortIntervals(vector<Interval>& intervals) {
    // 按结束时间排序
    sort(intervals.begin(), intervals.end());
    
    // 或按开始时间排序
    sort(intervals.begin(), intervals.end(), 
         [](const Interval& a, const Interval& b) {
             return a.start < b.start;
         });
}
C++贪心算法 区间问题专题 2025年5月10日

2.3 区间问题的数据结构

  • 常用数据结构：

    • 数组/向量：存储区间集合
    • 优先队列/堆：维护区间的动态排序
    • 线段树：处理区间查询和更新
    • 扫描线算法：处理区间的开始和结束事件

  • 区间表示方法：

    // 方法1：使用pair
vector<pair<int, int>> intervals;

// 方法2：使用自定义结构体
struct Interval {
    int start;
    int end;
    // 可能的其他属性
};
vector<Interval> intervals;

// 方法3：使用类
class Interval {
public:
    int start;
    int end;
    Interval(int s, int e) : start(s), end(e) {}
};
C++贪心算法 区间问题专题 2025年5月10日

3. 区间调度问题

3.1 区间调度问题定义

  • 问题描述：

    • 给定n个区间 [start_i, end_i]，表示n个活动的开始和结束时间
    • 目标：选择最大数量的互不重叠的区间

  • 实际应用：

    • 会议室安排
    • 课程表设计
    • 资源分配
    • 任务调度

  • 贪心策略：

    • 按照区间的结束时间进行排序
    • 每次选择结束时间最早且与已选区间不冲突的区间

  • 直觉理解：

    • 选择结束早的活动，可以为后面的活动留出更多的时间和空间
    • 这样可以最大化可以安排的活动数量
C++贪心算法 区间问题专题 2025年5月10日

3.2 区间调度算法实现

// LeetCode 435: 无重叠区间
// 返回需要移除的区间数量
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 = 1;  // 至少保留一个区间
    int end = intervals[0][1];  // 当前选择区间的结束时间
    
    // 贪心选择不重叠的区间
    for (int i = 1; i < intervals.size(); i++) {
        if (intervals[i][0] >= end) {
            // 当前区间与上一个选择的区间不重叠
            count++;
            end = intervals[i][1];
        }
    }
    
    // 返回需要移除的区间数量
    return intervals.size() - count;
}

算法步骤：

  1. 按区间结束时间排序
  2. 选择第一个区间（结束最早）
  3. 遍历剩余区间：
    • 如果当前区间与上一个选择的区间不重叠，选择它
    • 否则跳过

时间复杂度：

  • 排序：O(n log n)
  • 遍历：O(n)
  • 总体：O(n log n)

空间复杂度：

  • O(1)，不需要额外空间（不考虑排序）
C++贪心算法 区间问题专题 2025年5月10日

3.3 区间调度问题变种

1. 带权重的区间调度

  • 每个区间有一个权重/价值
  • 目标：选择不重叠区间，使总权重最大
  • 解法：动态规划（不再是简单贪心）

2. 需要多个资源的区间调度

  • 例如：需要多个会议室
  • 目标：使用最少的资源完成所有任务
  • 解法：优先队列 + 贪心

3. 区间调度最小化冲突

  • 目标：移除最少的区间，使剩余区间不重叠
  • 解法：与基本问题等价，贪心算法
// LeetCode 253: 会议室 II
// 计算需要的最少会议室数量
int minMeetingRooms(vector<vector<int>>& intervals) {
    vector<int> starts, ends;
    for (auto& interval : intervals) {
        starts.push_back(interval[0]);
        ends.push_back(interval[1]);
    }
    
    // 分别对开始时间和结束时间排序
    sort(starts.begin(), starts.end());
    sort(ends.begin(), ends.end());
    
    int rooms = 0, endIdx = 0;
    for (int i = 0; i < starts.size(); i++) {
        // 当前会议开始前，有会议结束，释放会议室
        if (starts[i] >= ends[endIdx]) {
            endIdx++;
        } else {
            // 需要新的会议室
            rooms++;
        }
    }
    
    return rooms;
}
C++贪心算法 区间问题专题 2025年5月10日

3.4 区间调度问题实例

LeetCode 452: 用最少数量的箭引爆气球

问题描述：
在二维空间中有n个气球，每个气球由一个水平区间表示，即气球的直径。箭可以沿y轴垂直射出，一支箭可以引爆它所穿过的所有气球。求引爆所有气球所需的最小箭数。

分析：
这本质上是一个区间调度问题的变形。我们需要找到最少数量的点，使得每个区间至少包含一个点。

贪心策略：

  1. 按区间结束位置排序
  2. 每次选择一个区间的结束位置射箭
  3. 移除所有被该箭引爆的气球
  4. 重复直到所有气球都被引爆
C++贪心算法 区间问题专题 2025年5月10日

3.5 区间调度问题实例代码

// LeetCode 452: 用最少数量的箭引爆气球
int findMinArrowShots(vector<vector<int>>& points) {
    if (points.empty()) return 0;
    
    // 按结束位置排序
    sort(points.begin(), points.end(), 
         [](const vector<int>& a, const vector<int>& b) {
             return a[1] < b[1];
         });
    
    int arrows = 1;  // 至少需要一支箭
    int end = points[0][1];  // 第一支箭的位置
    
    // 贪心选择箭的位置
    for (int i = 1; i < points.size(); i++) {
        // 如果当前气球不能被之前的箭引爆
        if (points[i][0] > end) {
            arrows++;  // 需要新的箭
            end = points[i][1];  // 更新箭的位置
        }
    }
    
    return arrows;
}

算法分析：

  1. 按气球的右边界排序
  2. 初始化第一支箭的位置为第一个气球的右边界
  3. 遍历剩余气球：
    • 如果当前气球不能被之前的箭引爆（左边界大于箭的位置）
    • 则需要新的箭，位置为当前气球的右边界

时间复杂度：

  • 排序：O(n log n)
  • 遍历：O(n)
  • 总体：O(n log n)

空间复杂度：

  • O(1)，不需要额外空间（不考虑排序）
C++贪心算法 区间问题专题 2025年5月10日

4. 区间覆盖问题

4.1 区间覆盖问题定义

  • 问题描述：

    • 给定一个目标区间 [start, end] 和一组可选区间
    • 目标：选择最少的区间，使它们的并集完全覆盖目标区间

  • 实际应用：

    • 传感器覆盖
    • 监控系统设计
    • 网络覆盖规划
    • 资源分配

  • 贪心策略：

    1. 按区间的起始位置排序
    2. 在所有能覆盖当前位置的区间中，选择结束位置最远的区间
    3. 更新当前位置为所选区间的结束位置
    4. 重复直到覆盖整个目标区间或无法继续覆盖
C++贪心算法 区间问题专题 2025年5月10日

4.2 区间覆盖算法实现

// 区间覆盖问题
// intervals: 可选区间集合，每个区间为 [start, end]
// target: 目标区间 [start, end]
int minIntervalsCover(vector<vector<int>>& intervals, 
                      vector<int>& target) {
    // 按起始位置排序
    sort(intervals.begin(), intervals.end());
    
    int count = 0;  // 选择的区间数量
    int currentPos = target[0];  // 当前需要覆盖的位置
    int i = 0;
    
    while (currentPos < target[1]) {
        int maxEnd = currentPos;  // 当前可达到的最远位置
        
        // 找出所有能覆盖currentPos的区间中，结束位置最远的区间
        while (i < intervals.size() && 
               intervals[i][0] <= currentPos) {
            maxEnd = max(maxEnd, intervals[i][1]);
            i++;
        }
        
        // 如果没有找到能覆盖currentPos的区间
        if (maxEnd == currentPos) {
            return -1;  // 无法完全覆盖目标区间
        }
        
        count++;  // 选择一个新区间
        currentPos = maxEnd;  // 更新当前位置
    }
    
    return count;
}

算法步骤：

  1. 按区间起始位置排序
  2. 初始化当前位置为目标区间的起始位置
  3. 循环直到覆盖整个目标区间：
    • 在所有起始位置≤当前位置的区间中
    • 选择结束位置最远的区间
    • 更新当前位置为所选区间的结束位置
    • 计数加一

时间复杂度：

  • 排序：O(n log n)
  • 遍历：O(n)
  • 总体：O(n log n)

空间复杂度：

  • O(1)，不需要额外空间（不考虑排序）
C++贪心算法 区间问题专题 2025年5月10日

4.3 区间覆盖问题实例

LeetCode 1024: 视频拼接

问题描述：
你将会获得一系列视频片段，每个片段都由一个区间表示，即片段的开始和结束时间。我们希望将这些片段拼接成覆盖整个 [0, time] 区间的一个视频。

返回所需片段的最小数目。如果无法完成该任务，则返回 -1。

分析：
这是一个典型的区间覆盖问题。我们需要选择最少的视频片段，使它们能够覆盖从0到time的整个时间线。

贪心策略：

  1. 按照片段的开始时间排序
  2. 在所有能覆盖当前位置的片段中，选择结束时间最远的片段
  3. 更新当前位置，重复直到覆盖整个时间线或无法继续覆盖
C++贪心算法 区间问题专题 2025年5月10日

4.4 区间覆盖问题实例代码

// LeetCode 1024: 视频拼接
int videoStitching(vector<vector<int>>& clips, int time) {
    // 按开始时间排序，如果开始时间相同，按结束时间降序
    sort(clips.begin(), clips.end(), 
         [](const vector<int>& a, const vector<int>& b) {
             return a[0] < b[0] || 
                   (a[0] == b[0] && a[1] > b[1]);
         });
    
    int count = 0;
    int currEnd = 0;  // 当前覆盖的结束位置
    int i = 0;
    
    while (currEnd < time) {
        int maxEnd = currEnd;
        
        // 找出所有能覆盖currEnd的片段中，结束时间最远的片段
        while (i < clips.size() && clips[i][0] <= currEnd) {
            maxEnd = max(maxEnd, clips[i][1]);
            i++;
        }
        
        // 如果没有找到能覆盖currEnd的片段
        if (maxEnd == currEnd) {
            return -1;  // 无法完全覆盖
        }
        
        count++;  // 选择一个新片段
        currEnd = maxEnd;  // 更新当前覆盖的结束位置
        
        // 如果已经覆盖了整个时间线
        if (currEnd >= time) {
            return count;
        }
    }
    
    return count;
}

算法分析：

  1. 按片段的开始时间排序（开始时间相同时按结束时间降序）
  2. 初始化当前覆盖的结束位置为0
  3. 循环直到覆盖整个时间线：
    • 在所有开始时间≤当前结束位置的片段中
    • 选择结束时间最远的片段
    • 更新当前覆盖的结束位置
    • 计数加一
  4. 如果无法继续覆盖，返回-1

时间复杂度：

  • 排序：O(n log n)
  • 遍历：O(n)
  • 总体：O(n log n)

空间复杂度：

  • O(1)，不需要额外空间（不考虑排序）
C++贪心算法 区间问题专题 2025年5月10日

5. 区间合并问题

5.1 区间合并问题定义

  • 问题描述：

    • 给定一组可能重叠的区间
    • 目标：合并所有重叠的区间，返回一个不重叠的区间集合

  • 实际应用：

    • 日程安排合并
    • 数据区间合并
    • 时间段整合
    • 资源占用分析

  • 贪心策略：

    1. 按区间的起始位置排序
    2. 初始化结果集为空
    3. 遍历排序后的区间：
      • 如果结果集为空或当前区间与结果集最后一个区间不重叠，直接添加
      • 否则，合并当前区间与结果集最后一个区间
C++贪心算法 区间问题专题 2025年5月10日

5.2 区间合并算法实现

// LeetCode 56: 合并区间
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty()) return {};
    
    // 按起始位置排序
    sort(intervals.begin(), intervals.end());
    
    vector<vector<int>> result;
    result.push_back(intervals[0]);
    
    for (int i = 1; i < intervals.size(); i++) {
        // 获取结果集中最后一个区间
        vector<int>& last = result.back();
        
        // 当前区间的起始位置
        int currStart = intervals[i][0];
        // 当前区间的结束位置
        int currEnd = intervals[i][1];
        
        // 如果当前区间与最后一个区间重叠
        if (currStart <= last[1]) {
            // 合并区间，更新结束位置
            last[1] = max(last[1], currEnd);
        } else {
            // 不重叠，直接添加到结果集
            result.push_back(intervals[i]);
        }
    }
    
    return result;
}

算法步骤：

  1. 按区间起始位置排序
  2. 初始化结果集，添加第一个区间
  3. 遍历剩余区间：
    • 如果当前区间与结果集最后一个区间重叠
    • 则合并这两个区间（更新结束位置）
    • 否则，将当前区间添加到结果集

时间复杂度：

  • 排序：O(n log n)
  • 遍历：O(n)
  • 总体：O(n log n)

空间复杂度：

  • O(n)，用于存储结果集

重叠条件：

  • 两个区间 [a, b] 和 [c, d] 重叠的条件是：
  • c ≤ b（第二个区间的起始位置 ≤ 第一个区间的结束位置）
C++贪心算法 区间问题专题 2025年5月10日

5.3 区间合并问题变种

1. 插入区间

  • 给定一组不重叠的区间和一个新区间
  • 目标：将新区间插入并合并重叠区间
  • 解法：找到新区间的插入位置，合并重叠区间

2. 区间列表的交集

  • 给定两个区间列表
  • 目标：计算两个列表的交集
  • 解法：双指针法，比较两个列表的区间

3. 区间列表的补集

  • 给定一组区间和一个范围
  • 目标：计算范围内不被区间覆盖的部分
  • 解法：合并区间后，计算相邻区间之间的空隙
// LeetCode 57: 插入区间
vector<vector<int>> insert(vector<vector<int>>& intervals, 
                          vector<int>& newInterval) {
    vector<vector<int>> result;
    int i = 0, n = intervals.size();
    
    // 添加所有在新区间之前且不重叠的区间
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.push_back(intervals[i++]);
    }
    
    // 合并所有与新区间重叠的区间
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = min(newInterval[0], intervals[i][0]);
        newInterval[1] = max(newInterval[1], intervals[i][1]);
        i++;
    }
    
    // 添加合并后的新区间
    result.push_back(newInterval);
    
    // 添加所有在新区间之后的区间
    while (i < n) {
        result.push_back(intervals[i++]);
    }
    
    return result;
}
C++贪心算法 区间问题专题 2025年5月10日

5.4 区间合并问题实例

LeetCode 986: 区间列表的交集

问题描述：
给定两个由一些闭区间组成的列表，每个区间列表都是成对不相交的，并且已经排序。返回这两个区间列表的交集。

分析：
这个问题要求我们找出两个区间列表中重叠的部分。由于两个列表都已经排序，我们可以使用双指针法来解决。

算法思路：

  1. 使用两个指针分别遍历两个区间列表
  2. 对于当前两个区间，计算它们的交集（如果存在）
  3. 将交集添加到结果中
  4. 移动指向结束位置较小的区间的指针
  5. 重复直到遍历完一个列表
C++贪心算法 区间问题专题 2025年5月10日

5.5 区间合并问题实例代码

// LeetCode 986: 区间列表的交集
vector<vector<int>> intervalIntersection(
    vector<vector<int>>& firstList, 
    vector<vector<int>>& secondList) {
    
    vector<vector<int>> result;
    int i = 0, j = 0;
    
    while (i < firstList.size() && j < secondList.size()) {
        // 计算两个区间的交集
        int low = max(firstList[i][0], secondList[j][0]);
        int high = min(firstList[i][1], secondList[j][1]);
        
        // 如果存在交集
        if (low <= high) {
            result.push_back({low, high});
        }
        
        // 移动指向结束位置较小的区间的指针
        if (firstList[i][1] < secondList[j][1]) {
            i++;
        } else {
            j++;
        }
    }
    
    return result;
}

算法分析：

  1. 使用双指针同时遍历两个区间列表
  2. 对于当前两个区间，计算它们的交集：
    • 交集的起始位置 = 两个区间起始位置的最大值
    • 交集的结束位置 = 两个区间结束位置的最小值
  3. 如果交集有效（起始位置 ≤ 结束位置），添加到结果中
  4. 移动指向结束位置较小的区间的指针
  5. 重复直到遍历完一个列表

时间复杂度：

  • O(m + n)，其中m和n是两个列表的长度

空间复杂度：

  • O(m + n)，用于存储结果（最坏情况）
C++贪心算法 区间问题专题 2025年5月10日

6. 区间问题变种

6.1 带权重的区间问题

  • 问题描述：

    • 每个区间除了起始和结束时间外，还有一个权重/价值
    • 目标：选择不重叠的区间，使总权重最大

  • 解决方法：

    • 这类问题通常需要使用动态规划而非简单贪心
    • 状态定义：dp[i] 表示考虑前i个区间能获得的最大权重
    • 状态转移：dp[i] = max(dp[i-1], dp[j] + weight[i])，其中j是最大的满足区间j与区间i不重叠的索引

  • 算法框架：

    // 按结束时间排序区间
sort(intervals.begin(), intervals.end());

// 动态规划
vector<int> dp(n + 1);
for (int i = 1; i <= n; i++) {
    // 找到与当前区间不重叠的最近区间
    int j = binarySearch(intervals, i);
    // 选择或不选择当前区间
    dp[i] = max(dp[i-1], dp[j] + weight[i-1]);
}
C++贪心算法 区间问题专题 2025年5月10日

6.2 区间问题与扫描线算法

扫描线算法：

  • 将区间的起点和终点看作独立的事件
  • 按照事件的发生顺序处理
  • 适用于求区间的并集、交集等问题

应用场景：

  • 计算区间覆盖的总长度
  • 求最大重叠区间数
  • 天际线问题

基本步骤：

  1. 将所有区间的起点和终点转换为事件
  2. 按照事件的位置排序
  3. 扫描所有事件，维护当前状态
  4. 根据状态变化计算结果
// LeetCode 218: 天际线问题的扫描线解法
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    // 创建关键点：(x, height)
    // 左端点高度为负值，表示进入建筑物
    // 右端点高度为正值，表示离开建筑物
    vector<pair<int, int>> points;
    for (auto& b : buildings) {
        points.push_back({b[0], -b[2]});  // 左端点
        points.push_back({b[1], b[2]});   // 右端点
    }
    
    // 按x坐标排序，x相同时按高度排序
    sort(points.begin(), points.end());
    
    vector<vector<int>> result;
    multiset<int> heights = {0};  // 当前所有高度，初始包含地平线
    int prevHeight = 0;
    
    for (auto& p : points) {
        if (p.second < 0) {
            // 左端点，添加高度
            heights.insert(-p.second);
        } else {
            // 右端点，移除高度
            heights.erase(heights.find(p.second));
        }
        
        // 当前最高点
        int currHeight = *heights.rbegin();
        
        // 如果高度变化，添加关键点
        if (currHeight != prevHeight) {
            result.push_back({p.first, currHeight});
            prevHeight = currHeight;
        }
    }
    
    return result;
}
C++贪心算法 区间问题专题 2025年5月10日

6.3 区间问题与线段树

  • 线段树：

    • 一种用于处理区间查询和更新的数据结构
    • 每个节点代表一个区间
    • 支持快速的区间操作

  • 适用场景：

    • 区间最值查询
    • 区间和查询
    • 区间更新
    • 动态区间操作

  • 线段树操作：

    • 构建：O(n)
    • 查询：O(log n)
    • 更新：O(log n)

  • 区间问题应用：

    // 线段树节点
struct SegmentTreeNode {
    int start, end;  // 区间范围
    int max;         // 区间最大值
    SegmentTreeNode *left, *right;
    SegmentTreeNode(int s, int e) : start(s), end(e), max(0), 
                                   left(nullptr), right(nullptr) {}
};

// 构建线段树
SegmentTreeNode* buildTree(int start, int end) {
    if (start > end) return nullptr;
    
    SegmentTreeNode* root = new SegmentTreeNode(start, end);
    if (start == end) return root;
    
    int mid = start + (end - start) / 2;
    root->left = buildTree(start, mid);
    root->right = buildTree(mid + 1, end);
    return root;
}
C++贪心算法 区间问题专题 2025年5月10日

6.4 区间问题与差分数组

差分数组：

  • 用于高效处理区间更新操作
  • 对于原数组A，差分数组D满足：
    • D[0] = A[0]
    • D[i] = A[i] - A[i-1] (i > 0)
  • 区间更新：只需修改差分数组的两个位置

应用场景：

  • 区间增减操作
  • 区间覆盖计数
  • 航班预订统计

基本操作：

  • 构建差分数组：O(n)
  • 区间更新：O(1)
  • 还原原数组：O(n)
// LeetCode 1109: 航班预订统计
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
    // 差分数组
    vector<int> diff(n + 1, 0);
    
    // 处理每个预订
    for (auto& booking : bookings) {
        int first = booking[0];   // 起始航班
        int last = booking[1];    // 结束航班
        int seats = booking[2];   // 预订座位数
        
        // 区间更新
        diff[first - 1] += seats;  // 起点增加
        diff[last] -= seats;       // 终点减少
    }
    
    // 还原原数组（前缀和）
    vector<int> result(n, 0);
    result[0] = diff[0];
    for (int i = 1; i < n; i++) {
        result[i] = result[i - 1] + diff[i];
    }
    
    return result;
}

算法分析：

  • 时间复杂度：O(n + m)，其中n是航班数，m是预订数
  • 空间复杂度：O(n)

关键思想：

  • 差分数组可以将区间操作转化为两个点的操作
  • 通过前缀和还原原始数组
C++贪心算法 区间问题专题 2025年5月10日

7. 实战练习

7.1 练习1：会议室分配

  • 问题描述：

    • 给定一系列会议的开始和结束时间
    • 目标：找出安排所有会议所需的最少会议室数量

  • 示例：

    • 输入：[[0,30],[5,10],[15,20]]
    • 输出：2
    • 解释：需要两个会议室才能安排所有会议而不发生冲突

  • 解题思路：

    1. 将所有会议的开始和结束时间分别提取出来并排序
    2. 使用两个指针分别遍历开始和结束时间
    3. 当遇到开始时间时，需要一个新的会议室
    4. 当遇到结束时间时，释放一个会议室
    5. 跟踪过程中需要的最大会议室数量

  • 代码实现：

    int minMeetingRooms(vector<vector<int>>& intervals) {
    vector<int> starts, ends;
    for (auto& interval : intervals) {
        starts.push_back(interval[0]);
        ends.push_back(interval[1]);
    }
    
    sort(starts.begin(), starts.end());
    sort(ends.begin(), ends.end());
    
    int rooms = 0, endIdx = 0;
    for (int i = 0; i < starts.size(); i++) {
        if (starts[i] < ends[endIdx]) {
            rooms++;  // 需要新的会议室
        } else {
            endIdx++;  // 可以重用已结束的会议室
        }
    }
    
    return rooms;
}
C++贪心算法 区间问题专题 2025年5月10日

7.2 练习2：跳跃游戏

问题描述：

  • 给定一个非负整数数组，你最初位于数组的第一个位置
  • 数组中的每个元素代表你在该位置可以跳跃的最大长度
  • 判断你是否能够到达最后一个位置

示例：

  • 输入：[2,3,1,1,4]
  • 输出：true
  • 解释：从位置0跳到位置1，然后跳到位置4

贪心思路：

  • 维护一个变量表示当前能到达的最远位置
  • 遍历数组，不断更新最远可达位置
  • 如果当前位置已经超过了最远可达位置，则无法到达终点
  • 如果最远可达位置大于等于数组最后一个位置，则可以到达终点
// LeetCode 55: 跳跃游戏
bool canJump(vector<int>& nums) {
    int maxReach = 0;  // 当前能到达的最远位置
    
    for (int i = 0; i < nums.size(); i++) {
        // 如果当前位置已经超过了最远可达位置，则无法到达终点
        if (i > maxReach) {
            return false;
        }
        
        // 更新最远可达位置
        maxReach = max(maxReach, i + nums[i]);
        
        // 如果已经可以到达终点，提前返回
        if (maxReach >= nums.size() - 1) {
            return true;
        }
    }
    
    return true;  // 默认可以到达（处理空数组或只有一个元素的情况）
}

算法分析：

  • 时间复杂度：O(n)，只需遍历一次数组
  • 空间复杂度：O(1)，只使用常数额外空间

贪心策略：

  • 每次都尽可能地扩大可达范围
  • 只要当前位置可达，就考虑从该位置能跳到的最远距离
C++贪心算法 区间问题专题 2025年5月10日

7.3 练习3：加油站

LeetCode 134: 加油站

问题描述：
在一条环路上有N个加油站，第i个加油站有gas[i]升汽油。你有一辆油箱容量无限的汽车，从第i个加油站开往第i+1个加油站需要消耗cost[i]升汽油。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回-1。

示例：

  • 输入：gas = [1,2,3,4,5], cost = [3,4,5,1,2]
  • 输出：3
  • 解释：从加油站3出发，可以绕行一周

贪心思路：

  1. 如果总油量小于总消耗，则无解
  2. 否则，从第一个站开始尝试，如果中途油量变为负数，则从下一个站重新开始
  3. 由于总油量大于等于总消耗，必然存在一个起点可以绕行一周
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int totalGas = 0, totalCost = 0;
    int start = 0, tank = 0;
    
    for (int i = 0; i < gas.size(); i++) {
        totalGas += gas[i];
        totalCost += cost[i];
        tank += gas[i] - cost[i];
        
        if (tank < 0) {
            // 无法从start到i+1，尝试从i+1开始
            start = i + 1;
            tank = 0;
        }
    }
    
    return totalGas >= totalCost ? start : -1;
}
C++贪心算法 区间问题专题 2025年5月10日

7.4 练习4：分发糖果

问题描述：

  • n个孩子站成一排，每个孩子有一个评分值
  • 你需要按照以下要求给这些孩子分发糖果：
    1. 每个孩子至少分配到1个糖果
    2. 评分更高的孩子必须比他相邻的孩子获得更多的糖果
  • 求最少需要准备的糖果数量

示例：

  • 输入：[1,0,2]
  • 输出：5
  • 解释：分配方案为[2,1,2]

贪心思路：

  • 两次遍历，分别处理左规则和右规则
  • 左规则：如果右边孩子评分高于左边，右边孩子糖果数=左边孩子糖果数+1
  • 右规则：如果左边孩子评分高于右边，左边孩子糖果数=max(当前值, 右边孩子糖果数+1)
  • 最终每个位置取两次遍历的最大值
// LeetCode 135: 分发糖果
int candy(vector<int>& ratings) {
    int n = ratings.size();
    vector<int> candies(n, 1);  // 初始每个孩子分配1个糖果
    
    // 从左向右遍历，处理右边评分更高的情况
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }
    
    // 从右向左遍历，处理左边评分更高的情况
    for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candies[i] = max(candies[i], candies[i + 1] + 1);
        }
    }
    
    // 计算总糖果数
    int total = 0;
    for (int candy : candies) {
        total += candy;
    }
    
    return total;
}

算法分析：

  • 时间复杂度：O(n)，需要三次遍历
  • 空间复杂度：O(n)，需要一个数组存储每个孩子的糖果数

贪心策略：

  • 分解问题为满足左规则和右规则两个子问题
  • 分别解决后取最大值，确保两个规则都满足
C++贪心算法 区间问题专题 2025年5月10日

8. 总结与拓展

8.1 区间问题解题模板

  • 区间调度问题：

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

int count = 0;
int end = INT_MIN;

for (const auto& interval : intervals) {
    if (interval.start >= end) {
        count++;
        end = interval.end;
    }
}

  • 区间覆盖问题：

    // 按开始时间排序
sort(intervals.begin(), intervals.end());

int count = 0;
int currPos = target[0];

while (currPos < target[1]) {
    int maxEnd = currPos;
    int i = 0;
    
    while (i < intervals.size() && intervals[i][0] <= currPos) {
        maxEnd = max(maxEnd, intervals[i][1]);
        i++;
    }
    
    if (maxEnd == currPos) return -1;  // 无法覆盖
    
    count++;
    currPos = maxEnd;
}

  • 区间合并问题：

    // 按开始时间排序
sort(intervals.begin(), intervals.end());

vector<Interval> result;
result.push_back(intervals[0]);

for (int i = 1; i < intervals.size(); i++) {
    if (intervals[i].start <= result.back().end) {
        // 合并区间
        result.back().end = max(result.back().end, intervals[i].end);
    } else {
        // 添加新区间
        result.push_back(intervals[i]);
    }
}
C++贪心算法 区间问题专题 2025年5月10日

8.2 区间问题的进阶技巧

1. 事件点排序

  • 将区间的起点和终点看作独立事件
  • 按照位置排序后统一处理
  • 适用于求最大重叠区间数等问题

2. 优先队列优化

  • 使用优先队列维护动态变化的区间集合
  • 适用于需要动态选择最优区间的问题

3. 二分查找加速

  • 在已排序的区间集合中快速查找
  • 适用于大规模区间查询问题

4. 区间树数据结构

  • 线段树、区间树等高级数据结构
  • 适用于频繁区间查询和更新的场景
// 使用事件点技术求最大重叠区间数
int maxOverlap(vector<vector<int>>& intervals) {
    vector<pair<int, int>> events;
    
    // 将区间转换为事件
    for (auto& interval : intervals) {
        events.push_back({interval[0], 1});  // 开始事件
        events.push_back({interval[1], -1}); // 结束事件
    }
    
    // 按位置排序，位置相同时结束事件优先
    sort(events.begin(), events.end());
    
    int maxCount = 0, count = 0;
    for (auto& event : events) {
        count += event.second;  // 更新当前重叠数
        maxCount = max(maxCount, count);  // 更新最大重叠数
    }
    
    return maxCount;
}

优先队列示例：

// 使用优先队列解决会议室分配问题
int minMeetingRooms(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    priority_queue<int, vector<int>, greater<int>> endTimes;
    
    for (auto& interval : intervals) {
        if (!endTimes.empty() && endTimes.top() <= interval[0]) {
            endTimes.pop();  // 重用会议室
        }
        endTimes.push(interval[1]);  // 分配新会议室
    }
    
    return endTimes.size();
}
C++贪心算法 区间问题专题 2025年5月10日

8.3 区间问题与其他算法的结合

  • 区间DP：

    • 区间型动态规划，状态定义通常为dp[i][j]表示区间[i,j]的最优解
    • 适用于石子合并、戳气球等问题
    • 状态转移通常涉及枚举区间内的分割点

  • 区间问题与图论：

    • 将区间看作图中的节点，重叠关系看作边
    • 区间调度可以转化为图的最大独立集问题
    • 区间覆盖可以转化为图的最小路径覆盖问题

  • 区间问题与数学：

    • 区间问题常与数学中的集合论、测度论有关
    • 可以利用容斥原理解决某些区间计数问题
    • 区间的并、交、差等操作对应集合的基本运算

  • 区间问题与系统设计：

    • 文件系统的空间分配
    • 内存管理中的段式存储
    • 数据库中的范围查询优化
    • 网络带宽分配与QoS保证
C++贪心算法 区间问题专题 2025年5月10日

8.4 总结与实践建议

区间问题解题步骤：

  1. 识别问题类型

    • 区间调度、覆盖、合并还是其他变种？
    • 是否有额外约束或权重？

  2. 选择合适的贪心策略

    • 按开始时间、结束时间还是长度排序？
    • 是否需要特殊的排序规则？

  3. 设计数据结构

    • 简单数组还是需要高级数据结构？
    • 是否需要优先队列、线段树等？

  4. 处理边界情况

    • 空输入、单区间、完全重叠等特殊情况
    • 确保算法在各种情况下都能正确工作

  5. 优化算法

    • 是否可以减少时间或空间复杂度？
    • 是否有更简洁的实现方式？

实践建议：

  • 掌握基本模板：熟悉区间调度、覆盖、合并的基本算法模板

  • 理解贪心策略：深入理解不同贪心策略的适用条件和证明方法

  • 多做变种题目：通过练习不同变种题目，提高解决区间问题的灵活性

  • 结合实际应用：将区间问题与实际应用场景结合，加深理解

  • 系统化学习：将区间问题放在更广泛的算法体系中学习，如与动态规划、图论等结合

进阶学习方向：

  • 区间动态规划
  • 计算几何中的区间问题
  • 高级数据结构（线段树、树状数组等）
  • 区间问题在系统设计中的应用
C++贪心算法 区间问题专题 2025年5月10日

参考资料

C++贪心算法 区间问题专题 2025年5月10日

谢谢观看

联系方式

下节预告: 贪心算法之背包与分配问题

C++贪心算法 区间问题专题 2025年5月10日