18962 区间合并(c++)

Love The Way You Lie 2023-10-06 17:53 3阅读 0赞

## **18962 区间合并** ##

字节跳动面试题。

给出N个区间，请合并所有重叠的区间。比如\[10,30\],\[20,60\]，可以合并成\[10,60\]。

下面4个区间

\[\[10,30\],\[80,100\],\[150,180\],\[20,60\],\]

可以合并成3个区间

\[\[10,60\],\[80,100\],\[150,180\]\]

按区间左端点的次序输出合并后的所有区间。

### 输入格式 ###

第一行一个整数N(1<=N<=100000)。

第二行到第N+1行，每行2个整数，代表区间的左右端点。

### 输出格式 ###

按区间左端点的次序输出合并后的所有区间,每行输出一个区间。

### 输入样例 ###

4  
10 30  
80 100  
150 180  
20 60

输出样例

10 60  
80 100  
150 180

代码如下：思路请见注释

#include <iostream>
    #include <algorithm>
    using namespace std;
    struct node//定义结构体数组，记录区间的数值
    {
        
        int l;
        int r;
    } a[200005];
    int cmp(node x,node y)//自己定义排序方式
    {
        
        return x.l<y.l;
    }
    int main()
    {
        
        ios::sync_with_stdio(0);
        int i,n;
        cin >> n;
        for(i=1; i<=n; i++)//输入数据
            cin >> a[i].l>>a[i].r;
        sort(a+1,a+n+1,cmp);//对左值由小到大排序
        a[i+1].l=a[i].l;//防止最后一个比较不了，就跟自己进行比较
        a[i+1].r=a[i].r;
        int l1=a[1].l;//记录左右值
        int r1=a[1].r;
        for(i=1; i<=n; i++)//两个两个进行比较
        {
        
            if(a[i+1].l<=r1&&i+1<=n)//让下一个和上一个左值进行比较
            {
        
                r1=max(r1,a[i+1].r);//取左值较大的
                continue;//进行下一趟
            }
            cout << l1<<" "<<r1<< endl;//输出
            r1=a[i+1].r;//对下一次进行处理
            l1=a[i+1].l;
        }
        return 0;
    }

运行结果如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUxMjk3OTg3_size_16_color_FFFFFF_t_70_pic_center]

## 若有可以改进的地方，请及时指出！ ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUxMjk3OTg3_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20210604131251450.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUxMjk3OTg3,size_16,color_FFFFFF,t_70#pic_center