当前位置:首页 > 题解目录 > 正文内容

【题解】区间合并

亿万年的星光2个月前 (05-30)题解目录214

【题目描述】

给定n个闭区间[ai,bi],其中i=1,2,...n。任意两个相邻或相交或相邻的闭区间可以合并为一个闭区间。例如,[1,2]和[2,3]可以合并为[1,3]。

[1,3]和[2,4]可以合并为[1,4],但是[1,2]和[3,4]不可以合并。

我们的任务是判断这些区间是否可以最终合并为一个闭区间,如果可以,则将这个闭区间输出,否则输出no

【输入描述】

第一行为一个整数n,3<n<50000。表示输入区间的数量。

之后n行,在第i行上(1<=i<=n),为两个整数ai和bi,整数之间用一个空格分隔,表示区间[ai,bi] 

(其中1<=ai<=bi<=10000)

【输出描述】

输出一行,如果这些区间最终可以合并为一个闭区间,输出这些闭区间的左右边界,用单个空格隔开;否则输出no

【样例输入】

5
5 6
1 5
10 10
6 9
8 10

【样例输出】

1 10


【题目分析】

排序区间:首先将所有区间按照左端点从小到大排序。按顺序合并区间。


贪心合并:

初始化 merged_interval 为第一个区间。

遍历后续区间,如果当前区间与 merged相交或相邻,则更新 merged 的右端点为两者的最大值。

如果不能合并,则直接返回 no。

检查是否合并完成:如果最终 merged 包含了所有区间,则输出它;否则输出 no。



【参考答案】

#include <bits/stdc++.h>
using namespace std;
// 定义区间结构体
struct Interval {
    int start;
    int end;
};
Interval a[100000];
bool cmp(Interval a,Interval b){
	return a.start<b.start;
}

int main() {
    int n;
    cin >> n;
    // 输入区间
    for (int i = 0; i < n; i++) {
        cin >> a[i].start >> a[i].end;
    }
    sort(a, a+n,cmp);
    // 初始化合并区间
    Interval merged = a[0];
    bool canMergeAll = true;
    // 尝试合并
    for (int i = 1; i < n; i++) {
        if (a[i].start <= merged.end) {
            // 更新右端点
            if (a[i].end > merged.end) {
                merged.end = a[i].end;
            }
        } else {
            canMergeAll = false;
            break;
        }
    }

    // 输出结果
    if (canMergeAll) {
        cout << merged.start << " " << merged.end << endl;
    } else {
        cout << "no" << endl;
    }

    return 0;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【题解】建设病房

1.建设病房(build.cpp)【题目描述】2020年1月23日下午,武汉市建设局紧急召集中建三局等单位举行专题会议,要求参照2003年抗击非典期间北京小汤山医院模式,在武汉职工疗养院建设火神山医院...

【题解】导弹拦截

【题目描述】某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导...

字符全排列

【题目描述】给定一个由不同的小写字母组成的字符串,输出这个字符串的所有全排列。我们假设对于小写字母有‘a’ <‘b’ < … <‘y’<‘z’,而且给定的字符串中的字母已经按照...

【题解】尼科彻斯定理

【题目描述】 验证尼科彻斯定理,即:任何一个整数m的立方都可以写成m个连续奇数之和。【输入描述】任一正整数【输出描述】该数的立方分解为一串连续奇数的和【样例输入】13【样例输出】13*13*...

剪刀石头布

【题目描述】石头剪子布,是一种猜拳游戏。起源于中国,然后传到日本、朝鲜等地,随着亚欧贸易的不断发展它传到了欧洲,到了近现代逐渐风靡世界。简单明了的规则,使得石头剪子布没有任何规则漏洞可钻,单次玩法比拼...

小苹果(apple)

【题目描述】小 Y 的桌子上放着n个苹果从左到右排成一列,编号为从1到n。小苞是小 Y 的好朋友,每天她都会从中拿走一些苹果。每天在拿的时候,小苞都是从左侧第1个苹果开始、每隔2个苹果拿走2个苹果。随...