蓝桥杯-合并区间

差分 + 前缀和

本实现按非负整数坐标的覆盖情况合并连续整数段，相邻整数也会合并。例如 [1,2] 与 [3,4] 输出 [1,4]。它不等同于仅合并相交实数区间的算法；使用时需先确认题目的区间语义，且坐标上界应适合开数组。


import os
import sys

# 请在此输入您的代码
n = int(input())

nums = []
maxN = 0

for _ in range(n):
    left, right = map(int, input().split())
    nums.append([left, right])
    maxN = max(maxN, left, right)

# 差分数组
diff = [0] * (maxN + 2)

# 求差分数组
for start, end in nums:
    diff[start] += 1
    diff[end + 1] -= 1

# 求前缀和
N = len(diff)
pre = [0] * (N + 1)
for i in range(1, N + 1):
    pre[i] = pre[i-1] + diff[i-1]

l, r = 0, 0
isStart = True
for i, v in enumerate(pre):
    if v > 0 and isStart:
        l = r = i - 1
        isStart = not isStart
    elif v > 0 and not isStart:
        r = i - 1
    elif v <= 0 and not isStart:
        print(f"{l} {r}")
        l = r = 0
        isStart = not isStart