type
Post
status
Published
date
May 3, 2026
slug
qjtx
summary
tags
算法
category
icon
password
概述
区间贪心算法是解决区间调度问题的经典算法，核心思想是通过某种贪心策略选择区间，以达到最优解。这类问题通常涉及时间、空间等资源的分配与选择。
经典问题一：区间调度（最大不相交区间）
问题描述
给定n个区间 [start_i, end_i]，选择尽可能多的不相交区间。
贪心策略
按区间结束时间从小到大排序，每次选择结束时间最早的区间。
算法思路
- 将所有区间按结束时间升序排序
- 选择第一个区间（结束时间最早的）
- 遍历剩余区间，如果当前区间的开始时间大于等于上一个选中区间的结束时间，则选择该区间
正确性证明（交换论证法）
假设存在最优解OPT和贪心算法解GREEDY，且GREEDY不是最优解。我们可以通过交换论证证明贪心解的最优性：
- 设贪心算法选择的第一个区间为I₁，最优解选择的第一个区间为J₁
- 由于按结束时间排序，end(I₁) ≤ end(J₁)
- 可以用I₁替换J₁，得到的新解仍然是最优解
- 递归应用此论证，可证明贪心解是最优的
洛谷例题：P1803 凌乱的yyy / 线段覆盖
题目链接：https://www.luogu.com.cn/problem/P1803
题目描述：现在有n个区间，要求选出尽可能多的区间，使得这些区间两两不相交。
解题思路：
- 将区间按右端点从小到大排序
- 贪心选择右端点最小的区间
- 维护上一个选中区间的右端点，判断当前区间是否可选
经典问题二：区间覆盖（最少区间覆盖）
问题描述
给定一个区间 [l, r]，选择尽可能少的子区间完全覆盖该区间。
贪心策略
每次选择能覆盖当前位置且右端点最大的区间。
算法思路
- 将所有区间按左端点从小到大排序
- 从目标区间左端点开始，每次选择能覆盖当前位置且右端点最远的区间
- 更新当前位置为选中区间的右端点
- 重复直到覆盖整个目标区间
洛谷例题：P2082 区间覆盖（加强版）
题目链接：https://www.luogu.com.cn/problem/P2082
题目描述：给定n个闭区间和一个目标区间，用这n个区间覆盖目标区间，求最少需要多少个区间。
解题思路：
- 按左端点排序
- 从左到右贪心选择，每次选择能覆盖当前点且右端点最远的区间
- 注意处理无法覆盖的情况
经典问题三：区间选点（最少点覆盖）
问题描述
给定n个区间，选择尽可能少的点，使得每个区间都至少包含一个点。
贪心策略
按区间结束时间排序，每次在区间结束位置选点。
算法思路
- 将所有区间按结束时间升序排序
- 在第一个区间的结束位置选一个点
- 遍历剩余区间，如果当前区间的开始时间大于已选点的位置，则在该区间结束位置选新点
洛谷例题：P1250 种树
题目链接：https://www.luogu.com.cn/problem/P1250
题目描述：有一条公路，需要在这条公路的某些位置种树，使得每个要求的区间内至少有一棵树，求最少需要种多少棵树。
解题思路：
- 将区间按右端点排序
- 贪心地在每个需要覆盖的区间的右端点种树
- 使用数组记录已种树的位置
算法对比总结
问题类型 | 目标 | 排序策略 | 贪心选择 | 时间复杂度 | 空间复杂度 |
区间调度 | 最多不相交区间 | 按右端点升序 | 选择右端点最小的可用区间 | O(n log n) | O(1) |
区间覆盖 | 最少区间覆盖目标 | 按左端点升序 | 选择覆盖当前点且右端点最大的区间 | O(n log n) | O(1) |
区间选点 | 最少点覆盖所有区间 | 按右端点升序 | 在区间右端点选点 | O(n log n) | O(1) |
常见变体与技巧
1. 区间长度限制
2. 带权区间调度
3. 环形区间问题
算法复杂度分析
时间复杂度
- 排序阶段：O(n log n) - 所有区间贪心问题都需要排序
- 贪心选择阶段：O(n) - 单次遍历
- 总体复杂度：O(n log n)
空间复杂度
- 基础版本：O(1) - 原地操作，仅用常数空间
- 存储结果版本：O(n) - 需要存储选中的区间或点
- 动态规划版本：O(n) - 需要DP数组
实际应用场景
1. 资源调度
- 会议室分配：公司会议室预约系统，最大化会议室利用率
- CPU任务调度：操作系统进程调度，最小化等待时间
- 车辆调度：物流公司车辆路径规划
2. 网络优化
- 带宽分配：网络带宽资源的合理分配
- 信道分配：无线通信中信道的选择与分配
- 服务器负载均衡：分布式系统中任务分配
3. 生产制造
- 生产线调度：工厂生产任务的合理安排
- 设备维护：设备维护时间窗口的规划
- 质量控制：产品检测时间段的安排
常见陷阱与注意事项
1. 边界条件处理
2. 排序稳定性
3. 特殊情况处理
4. 数据类型选择
练习题推荐
入门级
进阶级
高级
总结
区间贪心算法是一类重要且实用的算法，其核心在于：
- 正确识别问题类型：明确是求最大值还是最小值
- 选择合适的排序策略：根据问题特点确定排序关键字
- 设计贪心选择策略：在每一步做出局部最优选择
- 证明算法正确性：通常使用交换论证法或数学归纳法
- 处理边界情况：注意区间的开闭性和特殊情况
掌握区间贪心算法不仅能够解决经典的区间问题，还能为解决更复杂的优化问题提供思路和基础。通过大量的练习和实际应用，可以加深对这些算法的理解和掌握。
- 作者:wzy
- 链接:https://wzyblogs.us.ci//article/qjtx
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
