火烧赤壁

GitHub跳转原题关系图返回列表

按左端点排序所有半开区间，线性合并相交区间并累加并集长度。

OJ: luogu

题目 ID: P1496

难度:普及-

标签:排序区间合并python

日期: 2026-07-16 17:48

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

给出若干左闭右开区间，求它们的并集总长度。

思路

把区间按左端点排序，维护当前合并段 [left, right)。新区间与它分离时结算旧长度，否则把 right 扩展到更远处。半开区间长度正好是 right - left。

Python 知识

  • 元组默认按第一项、第二项依次排序，sorted((l, r) ...) 不需要额外 key。
  • 生成器把整数流按两个一组构造成区间，减少中间代码。
  • max(right, end) 直接表达区间右端扩展。

代码

python
import sys


data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
intervals = sorted((next(data), next(data)) for _ in range(n))
left, right = intervals[0]
answer = 0

for start, end in intervals[1:]:
    if start > right:
        answer += right - left
        left, right = start, end
    else:
        right = max(right, end)

print(answer + right - left)

复杂度

时间复杂度 O(nlog⁡n)O(n\log n)，空间复杂度 O(n)O(n)。

总结

区间并集的标准模板是“排序后维护一个当前合并段”。