[题] 区间合并 #贪心 #队列

队列"/>

[题] 区间合并 #贪心 #队列

题目

区间合并

题解

称多个区间合并后的区间为：大区间。
操作：

1. 输入所有区间后，按左端点排序。
2. 维护一个装有区间的队列：
   对于新加入的区间，有以下两种情况：
   1.能合并。
   操作：合并，然后更新当前大区间的右端。
   2.不能合并。
   操作：结束上一个大区间，然后开始新的大区间。
3. 注意对第0个大区间和最后一个大区间的操作。

代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
void merge(vector<PII> &segs) {vector<PII> res;sort(segs.begin(), segs.end());int st = -2e9, ed = -2e9;for (auto seg : segs) {//不能合并：结束当前大区间，开始新的大区间。 if (ed < seg.first) {//第0个大区间不算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);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;
}