题解 | #剩下的树#

剩下的树

https://www.nowcoder.com/practice/f5787c69f5cf41499ba4706bc93700a2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;
vector<PII> segs;
int res;//被移除的树000


//合并区间
void merge(){
    sort(segs.begin(),segs.end());//排序,默认按左端点升序
    int bg = -1, ed = -1;
    for(auto seg : segs){
        if(ed >= seg.first){//有交集
            ed = max(ed, seg.second);
        }else{//无交集
            if(bg != -1){
                res += ed - bg + 1;
            }
            bg = seg.first;
            ed = seg.second;
        }
    }

    //加上最后一个区间
    res += ed - bg + 1;
}

int main() {
    int L, M;
    cin >> L >> M;
    while(M --){
        int a, b;
        scanf("%d%d", &a, &b);
        segs.push_back({a, b});
    }
    merge();
    cout << (L + 1) - res << endl;//一共有L+1棵树
    return 0;
}
// 64 位输出请用 printf("%lld")

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 13:47
机械打工仔:你自己匿名可以,这么好的公司就别给它匿名了
点赞 评论 收藏
分享
06-26 15:33
青岛工学院 Java
积极的秋田犬要冲国企:他现在邀请我明天面试
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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