题目解析和算法源码

华为OD机试 - 区间交集（Java & JS & Python）_区间交集python_伏城之外的博客-CSDN博客

题目描述

给定一组闭区间，其中部分区间存在交集。

任意两个给定区间的交集，称为公共区间(如:[1,2],[2,3]的公共区间为[2,2]，[3,5],[3,6]的公共区间为[3,5])。

公共区间之间若存在交集，则需要合并(如:[1,3],[3,5]区间存在交集[3,3]，需合并为[1,5])。

按升序排列输出合并后的区间列表。

输入描述

一组区间列表，

区间数为 N: 0<=N<=1000;

区间元素为 X: -10000<=X<=10000。

输出描述

升序排列的合并区间列表

备注

• 区间元素均为数字，不考虑字母、符号等异常输入。
• 单个区间认定为无公共区间。

用例1

输入

4
0 3
1 3
3 5
3 6

输出

1 5

说明

[0,3]和[1,3]的公共区间为[1,3]，

[0,3]和[3,5]的公共区间为[3,3]，

[0,3]和[3,6]的公共区间为[3,3]，

[1,3]和[3,5]的公共区间为[3,3]，

[1,3]和[3,6]的公共区间为[3,3]，

[3,5]和[3,6]的公共区间为[3,5]，

公共区间列表为[[1,3],[3,3],[3,5]]；

[1,3],[3,3],[3,5]存在交集，须合并为[1,5]。

用例2

输入

4
0 3
1 4
4 7
5 8

输出

1 3
4 4 
5 7

用例3

输入

2
1 2
3 4

输出

None

说明

[1,2]和[3,4]无交集