首页 > 试题广场 >

IP段合并

[编程题]IP段合并
  • 热度指数：1475 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
一个数字段由首尾两个数字标识，表示一个自然数集合，
比如数字段[beg, end)表示从beg到end之间的所有自然数，
包含beg，但不包含end。

有若干个数字段，这些数字段之间可能有重叠，
怎么把这些数字段合并去重，用最少个数的数字段来表示。

合并前后，整个集合包含的数字不发生变化。



输入描述:
第一行为数字N，表示接下来有N个数字段(N<=100000)
第二行开始一共有N行，每行两个数字，分别表示一个数字段的beg和end
(beg和end为无符号32位整数)


输出描述:
合并去重后形成的数字段集合，按升序排列。
示例1

输入

4 
3 8
3 7
4 6
7 9

输出

3 9
算法知识视频讲解
添加回答
C
午后与猫头像 午后与猫
int n;
    scanf("%d", &n);
    while(n > 100000)
    {
        printf("值过大，请重新输入\n");
        scanf("%d", &n);
    }
    // printf("%d\n", n);
    long int beg, end, temp;
    int i,j,s,k = 0;
    int arr[n][2];

    for(i = 0;i<n;i++)
    {
        scanf("%d %d", &beg, &end);
        if(beg > end)
        {
            temp = end;
            end = beg;
            beg = temp;
        }
        if(i == 0)
        {
            arr[0][0] = beg;
            arr[0][1] = end;
        }
        else
            for(k=j; k>=0;k--)
            {
                if(arr[k-1][0] >= beg && k > 0)
                {
                    arr[k][0] = arr[k-1][0];
                    arr[k][1] = arr[k-1][1];
                }
                else
                {
                    arr[k][0] = beg;
                    arr[k][1] = end;
                    break;
                }
               
            }
        j++;
        s = 0;
        for(k=1; k<j;k++)
        {
            if(arr[k][0] <= arr[s][1] && arr[k][1] > arr[s][1])
            {
                arr[s][1]=arr[k][1];
                for(int n=k; n<j;n++)
                {
                    arr[n][0]=arr[n+1][0];
                    arr[n][1]=arr[n+1][1];
                }
                j--;
                k--;
            }
            else if(arr[k][0] <= arr[s][1] && arr[k][1] <= arr[s][1])
            {
                for(int n=k; n<j;n++)
                {
                    arr[n][0]=arr[n+1][0];
                    arr[n][1]=arr[n+1][1];
                }
                j--;
                k--;
            }
            else if(arr[k][0] > arr[s][1])
            {
                s++;
            }
        }
       
    }

    for(int a=0; a<j;a++)
    {
        printf("%d ", arr[a][0]);
        printf("%d ", arr[a][1]);
        printf("\n");
    }
发表于 2022-09-08 23:05:10 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 深信服 测试工程师 PHP工程师 Java工程师
来自：深信服2019春招技术...
上传者：小小
难度：
1条回答 8547浏览

热门推荐

通过挑战的用户

相关试题

IP段合并

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号