区间合并算法

0X00 区间合并

803. 区间合并

from sys import stdin

def read():
  return list(map(int, stdin.readline().split()))
  
n = read()[0]
segs = [None] * n

for i in range(n):
  x, y = read()
  segs[i] = [x, y]

segs.sort()
res = []

st, ed = float("-inf"), float("-inf")
for x, y in segs:
  if ed < x:
    if st != float("-inf"): res.append([st, ed])
    st, ed = x, y
  else:
    ed = max(ed, y)
if st != float("-inf"):
  res.append([st, ed])

print(len(res))

57. 插入区间

import bisect
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        bisect.insort(intervals, newInterval)
        st, ed = float("-inf"), float("-inf")
        res = []
        for x, y in intervals:
            if ed < x:
                if st != float("-inf"): res.append([st, ed])
                st, ed = x, y
            else:
                ed = max(ed, y)
        if st != float("-inf"): res.append([st, ed])

        return res