区间操作——算法系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）

对多个一维区间进行覆盖、合并、选点，目标是最小化覆盖点数、最大化区间合并效率，每一步选择对区间操作最优的基准点 / 区间。

本教程以多个字符串处理贪心算法案例场景为例，让大家彻底理解以 “局部最优” 推导 “全局最优” 的核心逻辑，并掌握区间覆盖问题、区间合并问题、区间选点问题的原理及代码实现。

区间覆盖问题：给定一个目标区间和多个子区间，选择最少的子区间覆盖整个目标区间，策略是选包含当前起点且右端点最远的子区间，更新起点后重复操作。实际场景：监控摄像头安装（最少摄像头覆盖整条道路）、洒水车路线规划（最少洒水次数覆盖整个路段）。
区间合并问题：将重叠 / 相邻的区间合并为不重叠的区间，策略是先按区间左端点排序，再依次合并重叠区间（每一步保留当前合并后区间的最右端点）。实际场景：日程表的重叠事件合并、数据统计的时间区间合并。
区间选点问题：给定多个区间，选择最少的点，使得每个区间至少包含一个点，策略是选第一个区间的右端点，剔除包含该点的区间，重复操作。实际场景：考试安排（最少考场满足所有考试时间段）、公交站点设置（最少站点覆盖所有居民区的出行区间）。

教程目录导航

▼

排序问题

一、区间覆盖问题

问题描述：

市政部门需要对一条笔直的公路进行洒水作业。整条公路可以看作是数轴上的一条线段，起点为 0，终点为 20。
- 洒水车每次作业只能覆盖公路上的一个连续路段。现在给定你洒水车所有可用的作业区间列表。
- 请你计算并返回，要想完全覆盖整条公路（从 0 到 20，包括端点），最少需要安排多少次洒水作业？
注意：
- 洒水车的作业区间可以重叠。
- 保证输入的区间列表一定能够完全覆盖整条公路。
- 每次必须选择完整的作业区间，不能截断。
输入格式:
- 给定一个目标总路段 [0, 20]。
- 给定一个作业区间列表 [1,5], [0,3], [4,8], [7,12], [9,15], [14,20], [10,18]
输出格式:
- 洒水作业次数

算法解析：

作业区间按左端点升序排序；
每次选包含当前起点且右端点最远的作业区间，更新起点为该作业区间的右端点；
重复直到覆盖目标区间，或无法覆盖（返回 - 1）。


#include <iostream>
#include <vector>
using namespace std;

// 区间结构体：左端点、右端点
struct Interval {
    int start;
    int end;
    bool operator<(const Interval& other) const {
        return start < other.start; // 左端点升序
    }
};

// 区间覆盖：target-目标区间，intervals-作业区间列表，返回最少需要的子区间数
int intervalCover(Interval target, vector<Interval>& intervals) {
    sort(intervals.begin(), intervals.end());
    int n = intervals.size();
    int res = 0; // 选中的作业区间数
    int curStart = target.start; // 当前需要覆盖的起点
    int i = 0;
    int maxEnd = -1; // 本次能覆盖的最远右端点

    while (curStart < target.end) {
        // 找到所有包含curStart的作业区间中，右端点最远的
        while (i < n && intervals[i].start <= curStart) {
            maxEnd = max(maxEnd, intervals[i].end);
            i++;
        }
        if (maxEnd <= curStart) return -1; // 无法覆盖当前起点，失败
        res++;
        curStart = maxEnd; // 更新起点为最远右端点
    }
    return res;
}

int main() {
    // 测试：目标区间[0, 20]，作业区间列表
    Interval target = {0, 20};
    vector<Interval> intervals = {{1,5}, {0,3}, {4,8}, {7,12}, {9,15}, {14,20}, {10,18}};
    int res = intervalCover(target, intervals);
    if (res == -1) cout << "无法覆盖目标区间" << endl;
    else cout << "最少洒水作业次数：" << res << endl;

    return 0;
}

输出结果


最少洒水作业次数：6

二、区间合并问题

问题描述：

给定一个无序的日程事件列表，每个事件包含开始时间和结束时间（start 为事件开始时间，end 为事件结束时间，且保证 start < end）。请编写一个算法，将所有重叠或相邻的日程事件进行合并，返回合并后的有序日程列表。
输入格式:
- 给定一个无序的日程事件列表 [1,3],[2,6],[8,10],[15,18],[7,9]
输出格式:
- 输出有序日程列表 [1,6],[7,10],[15,18]
解释：[1,3] 和 [2,6] 重叠，合并为 [1,6]；[8,10] 和 [7,9] 重叠，合并为 [7,10]；[15,18] 无重叠，保留原事件。

算法解析：

核心思路分为 3 步，排序是合并的前提（无序的区间无法直接判断重叠），具体如下：

排序：将所有日程事件按开始时间 start 升序排列，若开始时间相同，按结束时间升序排列；
初始化结果集：将排序后的第一个事件加入结果列表，作为初始合并基准；
遍历合并：从第二个事件开始，依次与结果列表的最后一个事件比较：
- 若当前事件的 start ≤ 最后一个合并事件的 end（重叠 / 相邻）：合并两个事件，更新最后一个事件的 end 为两者 end 的最大值；
- 若当前事件的 start ＞最后一个合并事件的 end（无重叠）：将当前事件直接加入结果列表。


#include <iostream>
#include <vector>

using namespace std;

// 合并重叠/相邻日程事件的核心函数
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    // 处理边界情况：输入为空，直接返回空数组
    if (intervals.empty()) {
        return {};
    }

    // 步骤1：按事件开始时间升序排序（核心前提，无序无法直接合并）
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];  // 按start升序排列
    });

    // 步骤2：初始化结果集，加入第一个排序后的事件作为合并基准
    vector<vector<int>> merged;
    merged.push_back(intervals[0]);

    // 步骤3：遍历剩余事件，逐个判断并合并
    for (size_t i = 1; i < intervals.size(); ++i) {
        // 取结果集最后一个已合并的事件
        vector<int>& last = merged.back();
        // 当前待判断的事件
        const vector<int>& curr = intervals[i];

        if (curr[0] <= last[1]) {
            // 重叠/相邻，合并事件：更新结束时间为两者的最大值
            last[1] = max(last[1], curr[1]);
        } else {
            // 无重叠，直接将当前事件加入结果集
            merged.push_back(curr);
        }
    }

    return merged;
}

int main() {
    // 测试用例（与之前示例一致）
    vector<vector<int>> schedule = {{1,3},{2,6},{8,10},{15,18},{7,9}};
    vector<vector<int>> result = merge(schedule);

    // 打印合并后的结果
    cout << "合并后的日程表：";
    for (const auto& interval : result) {
        cout << "[" << interval[0] << "," << interval[1] << "] ";
    }
    cout << endl;

    // 测试边界情况：单个事件
    vector<vector<int>> single = {{5,8}};
    vector<vector<int>> singleRes = merge(single);
    cout << "单个事件合并结果：";
    for (const auto& interval : singleRes) {
        cout << "[" << interval[0] << "," << interval[1] << "] ";
    }
    cout << endl;

    return 0;
}

输出结果


合并后的日程表：[1,6] [7,10] [15,18]
单个事件合并结果：[5,8]

三、区间选点问题

问题描述：

某城市规划公交站点，已知全市有 n 个居民区的公交出行区间，每个区间用 [start, end] 表示（start 为居民区居民的最早乘车点，end 为最晚乘车点，居民只能在自己的区间内的站点乘车，且保证 start ≤ end）。请你规划最少数量的公交站点，使得每个居民区的出行区间内至少包含一个站点，输出最少站点数量及一个合法的站点位置方案。
输入格式:
- 给定一个出行区间列表 [1,3],[2,5],[4,7],[6,8]
输出格式:
- 最少站点数：2，站点位置：[3,7]
解释：
- 站点 3 覆盖区间 [1,3]、[2,5]；
- 站点 7 覆盖区间 [4,7]、[6,8]；
- 无更少站点能满足所有区间覆盖要求（如 1 个站点无法同时覆盖[1,3]和[6,8]）。

算法解析：

区间选点问题的最优贪心策略是按区间右端点升序排序，核心逻辑为：每次选择当前未覆盖区间的右端点作为站点，该策略能让单个站点覆盖尽可能多的后续区间，从而保证站点数量最少。

排序：将所有居民区出行区间按右端点 end 升序排列（若右端点相同，按左端点升序，不影响结果）；
初始化：记录已选站点列表（初始为空），标记当前待覆盖的第一个区间；
贪心选点：
- 取当前第一个未覆盖区间的右端点作为新站点，加入站点列表；
- 筛选出所有包含该站点的区间（即区间start ≤ 站点 ≤ end），标记为已覆盖；
- 重复上述操作，直到所有区间均被覆盖。


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 核心函数：计算最少公交站点数及站点位置
// 输入：intervals - 居民区出行区间集合
// 输出：pair<最少站点数, 站点位置列表>
pair<int, vector<int>> minBusStops(vector<vector<int>>& intervals) {
    vector<int> stops;  // 存储最终站点位置
    // 边界情况1：无居民区，直接返回0个站点
    if (intervals.empty()) {
        return {0, stops};
    }

    // 步骤1：按区间右端点升序排序（贪心策略的核心前提）
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];  // 按end升序，优先选右端点小的区间
    });

    // 步骤2：贪心选点
    int n = intervals.size();
    vector<bool> covered(n, false);  // 标记区间是否被覆盖，初始全未覆盖

    for (int i = 0; i < n; ++i) {
        if (!covered[i]) {  // 找到第一个未覆盖的区间
            int stop = intervals[i][1];  // 选其右端点作为站点（贪心核心）
            stops.push_back(stop);       // 加入站点列表
            // 标记所有包含该站点的区间为已覆盖
            for (int j = i; j < n; ++j) {
                if (intervals[j][0] <= stop && stop <= intervals[j][1]) {
                    covered[j] = true;
                }
            }
        }
    }

    // 返回：站点数 + 站点位置
    return {stops.size(), stops};
}

// 辅助函数：打印区间（方便测试输出）
void printIntervals(const vector<vector<int>>& intervals) {
    for (const auto& p : intervals) {
        cout << "[" << p[0] << "," << p[1] << "] ";
    }
    cout << endl;
}

int main() {
    // 测试用例1：示例输入
    vector<vector<int>> test1 = {{1,3},{2,5},{4,7},{6,8}};
    // 测试用例2：边界情况 - 单个居民区
    vector<vector<int>> test2 = {{5,9}};
    // 测试用例3：边界情况 - 所有区间重叠
    vector<vector<int>> test3 = {{2,6},{1,4},{3,5},{2,7}};
    // 测试用例4：边界情况 - 区间无重叠
    vector<vector<int>> test4 = {{1,2},{3,4},{5,6},{7,8}};

    // 遍历测试用例执行
    vector<vector<vector<int>>> tests = {test1, test2, test3, test4};
    for (int idx = 0; idx < tests.size(); ++idx) {
        cout << "======== 测试用例" << idx+1 << " ========" << endl;
        cout << "居民区出行区间：";
        printIntervals(tests[idx]);
        auto [cnt, stops] = minBusStops(tests[idx]);  // C++17及以上支持结构化绑定
        // 若编译器不支持C++17，替换为：
        // pair<int, vector<int>> res = minBusStops(tests[idx]);
        // int cnt = res.first;
        // vector<int> stops = res.second;
        cout << "最少站点数：" << cnt << "，站点位置：[";
        for (int i = 0; i < stops.size(); ++i) {
            cout << stops[i];
            if (i < stops.size()-1) cout << ",";
        }
        cout << "]" << endl << endl;
    }

    return 0;
}

输出结果


======== 测试用例1 ========
居民区出行区间：[1,3] [2,5] [4,7] [6,8]
最少站点数：2，站点位置：[3,7]

======== 测试用例2 ========
居民区出行区间：[5,9]
最少站点数：1，站点位置：[9]

======== 测试用例3 ========
居民区出行区间：[2,6] [1,4] [3,5] [2,7]
最少站点数：1，站点位置：[4]

======== 测试用例4 ========
居民区出行区间：[1,2] [3,4] [5,6] [7,8]
最少站点数：4，站点位置：[2,4,6,8]

返回顶部