区间调度问题的常见描述是给定N个区间，每个区间有开始时间和结束时间，要求选出尽可能多的区间，使得这些区间两两之间没有重叠部分，这是贪心算法的典型应用场景。解决这个问题的核心在于选择合理的贪心策略，常见的策略有按开始时间排序、按结束时间排序、按区间长度排序等，其中按结束时间升序排序的策略可以保证得到最优解。
贪心策略分析
为什么按结束时间排序能得到最多不重叠区间？我们可以假设已经选出了一个最优解集合，其中第一个结束的区间不是所有区间中结束最早的。此时把这个区间替换成结束最早的那个不重叠区间，得到的新解区间数量不会减少，因此结束最早的区间一定在最优解中。按照这个逻辑依次选取后续区间，每次选结束时间最早且开始时间不早于上一个选中区间结束时间的区间，就能得到全局最优解。
完整C++实现代码
下面的代码实现了区间调度问题的求解，包含区间定义、排序逻辑、贪心选择和结果输出部分：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 定义区间结构体，包含开始时间和结束时间
struct Interval {
int start;
int end;
};
// 比较函数，按区间结束时间升序排序
bool compareInterval(const Interval& a, const Interval& b) {
return a.end < b.end;
}
// 贪心算法求解最多不重叠区间数量
int greedyIntervalSchedule(vector<Interval>& intervals) {
if (intervals.empty()) {
return 0;
}
// 按结束时间排序
sort(intervals.begin(), intervals.end(), compareInterval);
int count = 1; // 至少选中第一个结束的区间
int lastEnd = intervals[0].end; // 记录上一个选中区间的结束时间
// 遍历后续区间
for (int i = 1; i < intervals.size(); i++) {
// 如果当前区间开始时间不早于上一个选中区间的结束时间，说明不重叠
if (intervals[i].start >= lastEnd) {
count++;
lastEnd = intervals[i].end;
}
}
return count;
}
int main() {
// 测试用例，包含6个区间
vector<Interval> intervals = {
{1, 3}, {2, 5}, {3, 6}, {6, 8}, {5, 7}, {8, 10}
};
int result = greedyIntervalSchedule(intervals);
cout << "最多可以选中的不重叠区间数量为：" << result << endl;
return 0;
}
代码逻辑说明
上述代码的核心逻辑分为三步：
- 首先将输入的区间按结束时间升序排列，这样每次优先处理结束早的区间
- 初始化选中数量为1，把第一个区间作为初始选中区间，记录它的结束时间
- 遍历排序后的剩余区间，只要当前区间的开始时间大于等于上一个选中区间的结束时间，就说明两个区间不重叠，可以选中当前区间，更新选中数量和最后结束时间
算法复杂度分析
这个实现的时间复杂度主要来自排序操作，排序的时间复杂度是O(n log n)，后续遍历的时间复杂度是O(n)，因此整体时间复杂度为O(n log n)，空间复杂度是O(1)（如果不考虑存储区间本身的空间）。这种复杂度对于大部分常规规模的区间调度问题都足够高效。
扩展思考
如果需要输出具体选中的区间，只需要在选中区间的时候把当前区间加入结果集合即可。另外如果问题变种要求选出最少数量的区间覆盖整个时间范围，贪心策略会有所不同，需要按开始时间排序后选择能覆盖当前未覆盖区域的最远结束区间，这类变种问题也可以基于贪心思想进行调整实现。