刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

3.区间合并
给定 n 个闭区间 [ai; bi]，其中i=1,2,...,n。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如，[1;2] 和 [2;3] 可以合并为 [1;3]，[1;3] 和 [2;4] 可以合并为 [1;4]，但是[1;2] 和 [3;4] 不可以合并。
我们的任务是判断这些区间是否可以最终合并为一个闭区间，如果可以，将这个闭区间输出，否则输出no。
时间限制：1000
内存限制：65536
输入
第一行为一个整数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

使用微信搜索喵呜刷题，轻松应对考试！

答案：

略

解析：

【喵呜刷题小喵解析】：本题是一道区间合并的题目，可以使用贪心算法来解决。首先，我们读入区间的数量n和每个区间的左右边界。然后，我们按照区间的左边界进行排序，这样可以保证我们在合并区间时，总是选择左边界最小的区间进行合并。接下来，我们遍历每个区间，如果当前区间和上一个合并的区间有交集，那么我们就将当前区间合并到上一个合并的区间中，更新上一个合并的区间的右边界为两个区间右边界的较大值。否则，我们就将当前区间作为一个新的合并的区间。最后，我们检查合并的区间的数量，如果只有一个区间，说明所有的区间都可以合并为一个区间，我们输出这个区间的左右边界。否则，说明所有的区间不能合并为一个区间，我们输出"no"。时间复杂度为O(nlogn)，其中n为区间的数量，我们需要对区间按照左边界进行排序。空间复杂度为O(n)，我们需要存储每个区间的左右边界和合并的区间。
创作类型：
原创

本文链接：3.区间合并 给定 n 个闭区间 [ai; bi]，其中i=1,2,...,n。任意两个相邻或相交

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share