Acwing 803.区间合并

大佬牛皮！额也来分享下额滴代码叭

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
typedef pair<int,int> PII;
PII a[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i].first,&a[i].second);
    sort(a+1,a+n+1);
    int ed=a[1].second,ans=0;
    for(int i=2;i<=n;i++)
    {
        if(ed>=a[i].first)ed=max(ed,a[i].second);
        else ans++,ed=a[i].second;
    }
    cout<<ans+1<<endl;
}

%%%

🙇

斯国一

可以

请问佬发的三个百分号代表什么意思哇

%是模，因此是膜拜

谢谢佬w

%%%

Orz

orz orz

写的很好！个人觉得非常容易理解

orz

为啥N 只开了 1e6

不错不错

你更厉害

这里的N是合并前的区间个数,其实根据这道题目的话开到1e5就够了QwQ

为什么a[]要从a[1]开始，为什么不能从a[0]开始

%%%

写的特别好，终于理解了，谢谢！

%%%

Orz，我也贡献一下自己的代码

#include <bits/stdc++.h>
using namespace std;
int n, cnt = 0;
struct S {
    int l, r;
} a[100010], ans[100010];
int cmp(S a, S b) {
    if (a.l == b.l) return a.r < b.r;
    return a.l < b.l;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].l, &a[i].r);
    sort(a + 1, a + 1 + n, cmp);
    ans[++cnt] = a[1];
    for (int i = 2; i <= n; i++) {
        if (a[i].l <= ans[cnt].r) ans[cnt].r = max(ans[cnt].r, a[i].r);
        else ans[++cnt] = a[i];
    }
    cout << cnt << endl;
    return 0;
}

用了结构体！后生可畏

还是这个好理解

超级清晰

为什么要那么排序佬

为了让左边界 l 升序排列

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;
const int N = 100010;

int n;
vector<PII> segs;

void merge(vector<PII> &segs)
{
    vector<PII> res;

    //将区间按左端点排序
    sort(segs.begin(), segs.end()); //pair的sort排序是默认先按第一个后按第二个排序

    //将st(start)和ed(end)初始化为负无穷
    int st = -2e9, ed = -2e9; //int的最小值为−2147483647，可以取−2e9代替，当然这道题的数据范围是-+1e9
    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); //如果是有交集的，右端取大的那个
    }

    //如果遍历到最后一个，上面的遍历进入的是else没有加入res，就把最后这个区间加入结果res
    if (st != -2e9) res.push_back({st, ed});

    segs = res; //将合并后的区间res重新赋值给segs
}

int main()
{
    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;
}

大佬，这个merge函数为啥参数要用引用呀？求解答

加了&才能修改到原始数据segs

声明调用

分享一下我的代码叭，感觉写的比较简介

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
const int N = 1e5 + 10;

int n,ed = -1e9 - 10,res = 0;
PII a[N];
int main(){
    scanf("%d", &n);
    for(int i = 0;i < n;i ++ )scanf("%d%d",&a[i].first,&a[i].second);
    sort(a,a + n);
    for(int i = 0;i < n;i ++ ){
        if(a[i].first > ed)res ++ ;
        ed = max(ed,a[i].second);
    }
    cout << res << "\n";
    return 0;
}

%%%orz，大佬注释好详细，赞

int st=-2e9,ed=-2e9 ;
本人比较菜，不懂为什么st,ed不直接取排序后第一个元素的首尾，而要取-2e9

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std ;
typedef pair<int,int> pii ;
vector<pii> nums,res ;
int main()
{
    int n ;
    scanf("%d",&n) ; 
    while(n--)
    {
        int l,r ; 
        scanf("%d%d",&l,&r) ;
        nums.push_back({l,r}) ;
    }
    sort(nums.begin(),nums.end()) ;                 //按左端点排序
    int st=nums[0].first,ed=nums[0].second ;        //ed代表区间结尾，st代表区间开头
    for(auto num:nums)                   
    {
        if(ed<num.first)                            //情况1：两个区间无法合并
        {
            res.push_back({st,ed}) ;                //区间1放进res数组
            st=num.first,ed=num.second ;            //维护区间2
        }
        //情况2：两个区间可以合并，且区间1不包含区间2，区间2不包含区间1
        else if(ed<num.second)  
            ed=num.second ;                         //区间合并
    }  
    //(实际上也有情况3：区间1包含区间2，此时不需要任何操作，可以省略)

    //注：排过序之后，不可能有区间2包含区间1

    if(st!=-2e9&&ed!=-2e9) res.push_back({st,ed});

    //考虑循环结束时的st,ed变量，此时的st,ed变量不需要继续维护，只需要放进res数组即可。因为这是最后的一个序列，所以不可能继续进行合并。

    /*
    for(auto r:res)
        printf("%d %d\n",r.first,r.second) ;
    puts("") ;
    */

    //(把上面的注释去掉，可以在调试时用)

    printf("%d",res.size()) ;           //输出答案
    return 0 ;
}

有道理，这样是可以AC的

int的最小值为$-2147483647$，所以取$-2e9$比较省事，可以代表int的最小值；

还有一些可以代表int最小值的数，例如-0x3f3f3f3f,-1<<30等

笔误，是-2147483648 （笑）

懂了，谢谢你

用st = -1e9 -10 ed = -1e9 - 10也能 AC ，题目中−10^9≤li≤ri≤10^9 ; 所以这里只要是构造一个初始的空区间，能覆盖取值范围即可，以防[-1000000000 -1000000000] 空区间；直接用int st = s[0].first , ed = s[0].second; int st = s[0].first , ed = s[0].second; 这样就用不着特判定空区间

-0x3f3f3f3f好像不是-2147483648

都表示负无穷的意思 没有很大的区别

知道了，-2e9省事才用，谢谢你

题目不是说$l$和$r$都是$-10^9$~$10^9$吗？为什么还能取到-2e9?

2e9 有点不好理解，我换了种写法，思想一样，代码更好懂：

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

typedef pair<int, int> p;
vector<p> v;

signed main(){
    int n, l, r;
    cin >> n;
    while(n--){
        cin >> l >> r;
        v.emplace_back(make_pair(l, r));
    }
    sort(v.begin(), v.end());
    vector<p> merge;
    for(auto& p : v){
        if(merge.empty()) merge.emplace_back(p);  //原来就空，直接放入
        else{
            if(p.first > merge.back().second)   //不重叠
                merge.emplace_back(p);
            else merge.back().second = max(merge.back().second, p.second);  //重叠，右端点取最右端的值
        }
    }
    cout << merge.size();

    return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
typedef struct len{
    int l,r;
    bool operator<(const len&t){
        if(l!=t.l)
        return l<t.l;
        else return r<t.r;
    } 
}LE;
LE q[100010];
int main()
{
    int n,cnt=1;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        q[i]={a,b};
    }
    sort(q,q+n);
    int t=q[0].r;
    for(int i=1;i<n;i++)
    {
        if(t>=q[i].l)
        {
            t=max(t,q[i].r);
        }else
        {
            cnt++;
            t=q[i].r;
        }
    }
    cout<<cnt;
    return 0;
}

简单易懂，分享一下

#include<bits/stdc++.h>
using namespace std;
#define N 100010
int main()
{
    int l[N],r[N];
    int n,cnt = 0;
    cin >> n;
    for(int i=0; i<n; i++)cin >> l[i] >> r[i];
    sort(l,l+n);
    sort(r,r+n);
    int nl = l[0];
    int nr = r[0];
    for(int i=1; i<n; i++)
    {
        if(l[i]<=nr)
        {
            nr = r[i];
        }
        else
        {
            //nl = l[i];
            nr = r[i];
            cnt++;
        }
    }
    cout << cnt+1;
    return 0;
}

else if直接写成else有影响吗? 排序后好像不会出现ed＞second的情况吧?

会出现的，那样的话ed就不用改变了。写else后面应该写成ed=max(ed,num.second)

有点不明白cpp语法，st和ed这个-2e9是指2×10^-9吗

指的是-2*10^9

代码对我这种蒟蒻来说太难理解了，比如说for(auto num:nums)指的是循环变量num从1一直到nums数组的结尾吗？

就是依次遍历nums的元素，num就是取出来的元素

好的谢谢dalao

也可以用for(int i=0;i<nums.size(),i++)来实现 然后取值用nums[i].first来取

贴一个结构体代码hh

#include<iostream> 
#include<algorithm>

using namespace std;

const int N = 100010;

int cnt;
struct Edges
{
    int l, r;
    bool operator< (const Edges& t)const
    {
        if(l != t.l) return l < t.l;
        else return r < t.r;
    }
}edges[N];

int main() 
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        int l, r;
        cin >> l >> r;
        edges[i].l = l;
        edges[i].r = r;
    }
    sort(edges, edges + n);

    int ed = -2e9;
    for(int i = 0; i < n; i ++) 
    {
        if(ed < edges[i].l)
        {
            cnt ++;
            ed = edges[i].r;
        }
        else ed = max(ed, edges[i].r);
    }
    cout << cnt;
    return 0;
}

# 这好像是贪心？

确实是诶

你写的太棒了，逻辑很清晰

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1e5 + 10;
struct Range {
    int l;
    int r;
}range[N];

bool compareByLeft(const Range& x1, const Range& x2)
{
    return x1.l < x2.l;
}

int main()
{
    int n;
    cin >> n;
    for(int i = 0 ; i < n; i ++)
        scanf("%d%d", &range[i].l, &range[i].r);

    sort(range, range + n, compareByLeft);

    int count = 1;
    int boundary = range[0].r;
    for(int i = 1; i < n; i ++) {
        if(range[i].l <= boundary)
            boundary = max(boundary, range[i].r);
        else {
            count ++;
            boundary = range[i].r;
        }
    }

    cout << count << endl;
    return 0;
}

鹈鹕户口ing

提供一个我个人认为更优雅的做法，不需要针对最后一个元素或第一个元素特判：

#include<bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;

int n, a, b;
int main(){
    scanf("%d", &n);
    vector<ii> intervals(n);
    for(int i = 0; i < n; i++){
        scanf("%d %d", &a, &b);
        intervals[i] = {a, b};
    }
    sort(intervals.begin(), intervals.end());
    vector<ii> ans;
    for(int i = 0; i < n; i++){
        if(ans.size()){
            auto &t = ans.back();
            int &x = t.first, &y = t.second, cx = intervals[i].first, cy = intervals[i].second;
            if(cx <= y){
                y = max(y, cy);
                x = min(x, cx);
                continue;
            }
        }
        ans.push_back(intervals[i]);
    }
    cout << ans.size() << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<vector<int>> intervals;
    vector<vector<int>> ans;

    while (n--) {
        int l, r;
        cin >> l >> r;
        intervals.push_back({l, r});
    }

    sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
        return a[0] < b[0];
    });

    for (auto& inter: intervals) {
        if (!ans.empty() && ans.back()[1] >= inter[0]) {
            ans.back()[1] = max(ans.back()[1], inter[1]);
        }else {
            ans.push_back(inter);
        }
    }

    cout << ans.size();
    // for (auto& a: intervals) {
    //     cout << a[0] << " " << a[1] << endl;
    // }
}

为何没有线段树？