首页 > Windows开发 > 详细

Acwing‘803. 区间合并

时间:2019-07-11 11:20:57      阅读:48      评论:0      收藏:0      [点我收藏+]

标签:接下来   back   msu   每次   minus   size   例如   fir   def   

https://www.acwing.com/problem/content/805/

给定 nn 个区间 [li,ri][li,ri],要求合并所有有交集的区间。

注意如果在端点处相交,也算有交集。

输出合并完成后的区间个数。

例如:[1,3]和[2,6]可以合并为一个区间[1,6]。

输入格式

第一行包含整数n。

接下来n行,每行包含两个整数 l 和 r。

输出格式

共一行,包含一个整数,表示合并区间完成后的区间个数。

数据范围

1n1000001≤n≤100000,
109liri109−109≤li≤ri≤109

输入样例:

5
1 2
2 4
5 6
7 8
7 9

输出样例:

3


思路:贪心。总的区间为n,每次合并一个区间,n--。注意处理边界问题:不能枚举到最后一个

#include <iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
typedef pair<int,int>pll;
vector<pll> all;
int main()
{
    int n;
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        int l,r;
        cin >> l >> r;
        all.push_back({l,r});
    }
    sort(all.begin(),all.end());
    int ans=n;
    for(int i=0;i<all.size()-1;i++)//不能枚举到最后一个
    {
        if(all[i].second>=all[i+1].first)
        {
            ans--;
            all[i+1].first=all[i].first;
            all[i+1].second=max(all[i+1].second,all[i].second);
        }
    }
    cout <<ans << endl;
    return 0;
}

 

 













Acwing‘803. 区间合并

标签:接下来   back   msu   每次   minus   size   例如   fir   def   

原文:https://www.cnblogs.com/wjc2021/p/11168312.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号