区间交集
标题：区间交集 | 时间限制：1秒 | 内存限制：262144K | 语言限制：不限
给定一组闭区间，其中部分区间存在交集。任意两个给定区间的交集，称为公共区间（如：[1,2],[2,3]的公共区间为[2,2]，[3,5],[3,6]的公共区间为[3,5]）。公共区间之间若存在交集，则需要合并（如：[1,3],[3,5]区间存在交集[3,3]，须合并为[1,5])。按升序排列输出合并后的区间列表。
import sys
ranges = []
for line in sys.stdin:
a = line.split()
left = int(a[0])
right = int(a[1])
ranges.append((left, right))
# ranges = \
# [[0, 3],
# [1, 3],
# [3, 5],
# [3, 6],]
# ranges = \
# [[0, 3],
# [1, 4],
# [4, 7],
# [5, 8],]
# ranges = \
# [[1, 2],
# [3, 4],]
ORI_LEN = len(ranges)
LEN = len(ranges)
pre_LEN = LEN + 1
# find out intersection
new_ranges = set()
for i in range(LEN):
for j in range(i + 1, LEN):
if ranges[i][1] >= ranges[j][0]:
left = max(ranges[i][0], ranges[j][0])
right = min(ranges[i][1], ranges[j][1])
if left <= right:
new_ranges.add((left, right))
ranges = list(new_ranges)
ranges.sort()
# print("new ranges:")
# print(new_ranges)
# print("ranges:")
# print(ranges)
# find out union
new_ranges = set()
LEN = len(ranges)
for i in range(LEN):
if ranges[i] == None:
continue
left = ranges[i][0]
right = ranges[i][1]
for j in range(i + 1, LEN):
if ranges[j] == None:
continue
if ranges[j][0] <= right:
right = max(right, ranges[j][1])
ranges[j] = None
else:
break
new_ranges.add((left, right))
ranges = list(new_ranges)
ranges.sort()
# print("ranges:")
# print(ranges)
if len(ranges) == 0:
print("None")
else:
for l, r in ranges:
print(f"{l} {r}")
data = [[0, 0] for _ in range(20000)]
while True:
try:
a, b = list(map(int, input().split(" ")))
data[a + 10000][0] += 1
data[b + 10000][1] += 1
except Exception as e:
break
tmp, is_empty = 0, 0
res = []
for i in range(len(data)):
if tmp <= 1 and tmp + data[i][0] >= 2:
print(i - 10000, end=" ")
if tmp + data[i][0] >= 2 and tmp + data[i][0] - data[i][1] <= 1:
print(i - 10000, end="\n")
is_empty = 1
tmp = tmp + data[i][0] - data[i][1]
if is_empty == 0:
print("None")
