蓝桥杯-合并区间

差分 + 前缀和


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 = 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