区间合并是一种常见的算法问题，通常在处理范围覆盖、时间调度、区间覆盖等问题时会用到。区间合并的目的是将一些有重叠或相邻的区间合并成一个更大的区间，从而简化问题的复杂性。
算法思想
给定一组区间，可能存在部分区间之间有重叠或相邻关系。区间合并的目标是将这些重叠或相邻的区间合并成一个大的区间。算法的基本思想是：先将所有区间按起始点排序，然后遍历区间并逐步合并重叠或相邻的区间。
算法流程
- 排序区间：
- 首先，按每个区间的起始点（左端点）进行排序。如果起始点相同，可以再按终止点（右端点）排序（可选）。
- 初始化结果集：
- 初始化一个空的结果集，用于存放合并后的区间。
- 遍历区间并进行合并：
- 逐一遍历排序后的区间。对于当前遍历的区间，如果结果集是空的，或者当前区间与结果集中最后一个区间没有重叠，则直接将当前区间添加到结果集中。
- 如果当前区间与结果集中最后一个区间有重叠，则将两个区间合并，更新结果集中最后一个区间的终止点为两个区间终止点的最大值。
- 输出结果：
- 遍历完成后，结果集中的区间即为合并后的区间。
算法模板
vector<pair<int, int>> mergeIntervals(vector<pair<int, int>>& vp) {vector<pair<int, int>> res; // 用于存储合并后的区间const int n = vp.size(); // 区间的数量// 如果没有区间，则直接返回空结果if (n == 0) return res;// Step 1: 按照区间的起始点进行排序// 排序的目的是让重叠的区间相邻，从而便于合并sort(vp.begin(), vp.end());// Step 2: 遍历排序后的区间并进行合并for (int i = 0; i < n; i++) {auto [l, r] = vp[i]; // 取出当前区间的起始点 l 和终止点 r// Step 3: 检查当前区间与下一个区间是否重叠// 如果下一个区间的起始点小于等于当前区间的终止点，则说明有重叠while (i + 1 < n and vp[i + 1].first <= r) {i++; // 移动到下一个区间r = max(r, vp[i].second); // 更新当前区间的终止点为两个区间终止点的最大值}// Step 4: 将合并后的区间添加到结果集中res.push_back({l, r});}// 返回合并后的区间列表return res;
}
例题
校门外的树 (nowcoder.com)
在一个长度为L的马路上，马路的两端分别位于数轴的0和L的位置。马路上种植着一排树，每两棵树之间的间隔为1米，可以认为数轴上的每个整数点（从0到L）都有一棵树，故总共有L + 1棵树。当前，有一些区域需要用来建设地铁，这些区域在数轴上的起始点和终止点均为整数。这些区域可能会有重叠的部分。在这些区域内的树木（包括区域起始和终止点上的树）需要被移走。
你的任务是计算在移走所有指定区域内的树木之后，马路上还剩下多少棵树。
#include <bits/stdc++.h>
using namespace std;int main(){int L,M;cin>>L>>M;vector<pair<int,int>> vp(M);for(auto&[l,r]:vp)cin>>l>>r;sort(vp.begin(),vp.end());vector<pair<int,int>> res;for(int i=0;i<M;i++){auto[l,r]=vp[i];while(i+1<M and vp[i+1].first<=r){i++;r = max(r, vp[i].second);}res.push_back({l,r});}int sum=L+1;for(auto[l,r]:res)sum-=(r-l+1);cout<<sum<<endl;return 0;
}
