20题区间合并如何成？

20.Acwing基础课第803题-简单-区间合并 题目描述 给定 n个区间 [li,ri]，要求合并所有有交集的区间。 注意如果在端点处相交，也算有交集。 输出合并完成后的区间个数。 例如：[1,3]和[2,6]可以合并为一个区间 [1,6]。 输入格式 第一行包含整数 n。 接下来 n行，每行包含两个整数 l 和 r。 输出格式 共一行，包含一个整数，表示合并区间完成后的区间个数。 数据范围 1≤n≤100000， −109≤li≤ri≤109 输入样例： 5 1 2 2 4 5 6 7 8 7 9 输出样例： 3 代码： #include <iostream> #include <vector> #include <algorithm> using namespace std; // 定义成对的整数类型，用来存储区间的左右端点（first=左端点，second=右端点） typedef pair<int, int> PII; /** * @brief 合并重叠/相邻的区间 * @param segs 传入存储所有原始区间的vector，合并结果会直接覆盖该vector */ void merge(vector<PII> &segs) { // 存储合并后的结果区间 vector<PII> res; // 核心步骤1：按区间左端点从小到大排序（区间合并的前提） sort(segs.begin(), segs.end()); // 初始化当前合并区间的起始(st)和结束(ed)，-2e9是极小值（小于题目中可能的区间范围） int st = -2e9, ed = -2e9; // 遍历所有排序后的区间 for (auto seg : segs) { // 情况1：当前区间和上一个合并区间无重叠（上一个区间的结束 < 当前区间的开始） int l = seg.first, r = seg.second; if (ed < l) // 无交集，保存当前区间 { // 如果不是初始的极小值区间（说明已有合并好的区间），加入结果集 if (st != -2e9) res.push_back({st, ed}); // 更新当前合并区间为新的未重叠区间 st = l, ed = r; } // 情况2：当前区间和上一个合并区间有重叠/相邻，更新合并区间的结束为两者最大值 else ed = max(ed, seg.second); } // 处理最后一个合并好的区间（避免遍历结束后遗漏） if (st != -2e9) res.push_back({st, ed}); // 将合并结果覆盖原区间数组 segs = res; } int main() { int n; // 读取区间的数量n scanf("%d", &n); // 存储所有原始区间的数组 vector<PII> segs; for (int i = 0; i < n; i ++ ) { int l, r; // 读取每个区间的左右端点 scanf("%d%d", &l, &r); // 将区间加入数组 segs.push_back({l, r}); } // 调用合并函数处理区间 merge(segs); // 输出合并后的区间数量（核心结果） cout << segs.size() << endl; return 0; }