点击查看代码
#include
#include
#include
using namespace std;
typedef pair PII;
vector segs;
void merge(vector& segs)
{
vector res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs) {
if (ed < seg.first) {
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
}
if (st != -2e9) res.push_back({st, ed});
segs = res;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++) {
int l, r;
scanf("%d %d", &l, &r);
segs.push_back({l, r});
}
merge(segs);
printf("%d", segs.size());
return 0;
}
- 将区间按照左端点进行排序，如果左端点相同，按右端点排序（sort 对 pai 排序的规则是，先按照第一个成员，再按照第二个成员）；
- 区间合并的三种情况：
① 新区间是原区间的子区间，新区间的右端点小于原区间右端点，这种情况不需要处理；
② 新区间和原区间有交集，需要合并，新区间的右端点大于原区间的右端点，需要把原区间右端点更新为新区间右端点；
③ 新区间和原区间没有交集，需要把区间更新，新区间左端点大于原区间右端点（这种情况要先判断，再判断①和②），将原区间存到 res 中，将原区间更新为新区间；