摘要
Title: 803. 区间合并
Tag: 区间合并
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

803. 区间合并

• 题意

  给定 n 个区间 [li,ri]，要求合并所有有交集的区间。
  注意如果在端点处相交，也算有交集。
  输出合并完成后的区间个数。
  例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。

• 思路

  板子题

  • 别忘了加最后那个区间
  • 统计区间时记得换起点和终点

• 代码

  n = int(input())
  INF = int(2e9)
  nums = []
  for i in range(n):
      x, y = map(int, input().split())
      nums.append([x, y])
  nums.sort()
  
  L, R = -INF, -INF
  res = 0
  for l, r in nums:
      if R < l:
          if L != -INF and R != -INF:
              res += 1
          L, R = l, r
      else:
          R = max(R, r)
  if L != -INF and R != -INF:
      res += 1
  print(res)