//给定多个区间 求有几个区间(将两重合区间合并成一个区间) #include<iostream> #include<algorithm> #include<vector> using namespace std; typedef pair<int,int> PII; vector<PII> a; int n; void merge(vector<PII> &a) { vector<PII> s; sort(a.begin(),a.end()); //先排序 int st=-1e9,en=-1e9; //初始化 左右端点为负 for(auto i:a) { if(en<i.first) //如果左端点大于目前右端点,则更新 { if(st!=-1e9) //这样写的话最后一个区间会存不上 ,因为没有下一个i.first>此区间的en,所以最后要加上最后那个区间 s.push_back({st,en}); st=i.first; en=i.second; } else en=max(en,i.second); //如果不大于 则说明i端点在此区间中 ,则更新右端点 } if(st!=-1e9) //既是将最后那个区间存进去也是防止一个区间都没有的情况 s.push_back({st,en}); a=s; } int main(void) { cin>>n; for(int i=0;i<n;i++) { int l,r; cin>>l>>r; a.push_back({l,r}); //存所有区间 } merge(a); //区间合并函数 cout<<a.size()<<endl; return 0; }
0.0分
0 人评分
字符串的输入输出处理 (C语言代码)浏览:2020 |
2005年春浙江省计算机等级考试二级C 编程题(3) (C语言代码)浏览:389 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:667 |
C语言程序设计教程(第三版)课后习题11.1 (C语言代码)浏览:687 |
不会做的浏览:873 |
C语言程序设计教程(第三版)课后习题7.1 (C语言代码)浏览:514 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:1195 |
关于float,double变量的几点说明浏览:1810 |
陈教主的三角形 (C语言代码)浏览:1142 |
前10名 (C语言代码)浏览:727 |