【题解】合并区间

合并区间

http://www.nowcoder.com/questionTerminal/0596b6232ce74b18b60ba0367d7f2492

先把区间按区间的起始位置从小到大排序,然后从前往后看一遍,如果下一个区间的开始比前一个区间的末尾要小。那么这两个区间就可以合并。

#include<iostream>
#include<algorithm>

using namespace std;

const int MAXN = 1e5+10;
struct node{
    int s,e;
}Interval[MAXN];
bool visit[MAXN];
bool cmp(node a,node b)
{
    if(a.s==b.s)
    {
        return a. e< b.e;
    }
    return a.s < b.s;
}
int main()
{
    int a,b;
    char c;
    int cnt = 0;
    while(cin >> a >> c >> b)
    {
         Interval[cnt].s = a;
         Interval[cnt].e = b;
         visit[cnt]= true;
         cnt++;
    }
    sort(Interval,Interval+cnt,cmp);
    for(int i = 1 ; i < cnt ; i++)
    {
        if(Interval[i].s <= Interval[i-1].e)//合并两个区间
        {
            Interval[i].s = min(Interval[i-1].s,Interval[i].s);
            Interval[i].e = max(Interval[i-1].e,Interval[i].e);
            visit[i-1]=false;
        }
    }
    for(int i = 0 ; i < cnt ; i++)
    {
        if(visit[i])
        {
            cout<<Interval[i].s<<","<<Interval[i].e<<" ";
        }
    }

    return 0;
}
全部评论

相关推荐

这算盘打的
程序员小白条:都这样的,都是潜规则,你自己说可以实习一年就行了,实习可以随便跑路的
点赞 评论 收藏
分享
程序员小白条:你是沟通了900个,不是投了900份简历,你能投900份,意味着对面都要回复你900次,你早就找到实习了,没亮点就是这样的,别局限地区,时间投的也要早,现在都要7月了
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务