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

【题解】区间合并

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

【题目描述】

给定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;
}


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

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

分享给朋友:

相关文章

【题解】2019 T2 公交换乘

【题目描述】著名旅游城市 B 市为了鼓励大家采用公共交通方式出行,推出了一种地铁换乘公交车的优惠方案:1、在搭乘一次地铁后可以获得一张优惠票,有效期为 45 分钟,在有效期内可以消耗这张优惠...

公路(road)

公路(road)

【题目描述】小苞准备开着车沿着公路自驾。公路上一共有n个站点,编号为从1 到n。其中站点i与站点i+1 的距离为vi公里。公路上每个站点都可以加油,编号为i 的站点一升油的价格为a...

【题解】BFS、DFS——走迷宫问题

【题目描述】给定一个 n×m的二维整数数组,用来表示一个迷宫,数组中只包含 0 或 1,其中 0 表示可以走的路,1 表示不可通过的墙壁。最初,有一个人位于左上角 (1,...

【题解】冒泡排序计数

【题目描述】考虑冒泡排序的一种实现。bubble-sort  (A[],  n)>   round  =  0>   while...

【算法】最短路径

【算法】最短路径

【题目描述】下图表示从城市A到城市H的交通图。从图中可以看出,从城市A到城市H要经过若干个城市。现在找出一条经过城市最少的一条路线。【输入描述】第一行一个整数n,表示几个城市。接下来2~n+1行,表示...

【题解】基因锁

【题目描述】小X终于意识到需要花大力气减重了,他询问了若干个减重专家后决定采用最适合年轻人的运动减重方案,考虑再三,小X最终选择了打羽毛球的方式,一个原因是小X的小伙伴大都喜欢打羽毛球,其次是打羽毛球...