1 Star 0 Fork 0

wangliewei/acwing_algothrim

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
803intervalMerge.cpp 964 Bytes
一键复制 编辑 原始数据 按行查看 历史
wangliewei 提交于 2021-08-19 11:15 . add topK
//
// Created by wangliewei on 2021/8/19.
//
/*
贪心:
1、按区间左端点排序
2、维护一个区间,分三种情况更新
*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
vector<PII> segs;
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) {
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;
cin >> n;
for (int i = 0; i < n; i++) {
int l,r;
cin >> l >> r;
segs.push_back({l,r});
}
merge(segs);
cout << segs.size() << endl;
return 0;
}
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/wangliewei/yxc_algothrim.git
git@gitee.com:wangliewei/yxc_algothrim.git
wangliewei
yxc_algothrim
acwing_algothrim
master

搜索帮助