https://leetcode.com/contest/weekly-contest-293/problems/count-integers-in-intervals/
本身不是什么很精巧的题目，合并区间就完事了，但是自己调试了很久，还是对于边界的处理不够优雅和全面。
记下这道题的解法，回顾左右边界值的考虑。
题目解析就不写了，还是看代码来得实在。

个人解答

  1. from sortedcontainers import SortedList
  3. class CountIntervals:
  5.     def __init__(self):
  6.         self.cnt = 0
  7.         self.intervals = SortedList([(-inf, -inf), (inf, inf)])
  9.     def add(self, left: int, right: int) -> None:
  10.         i = self.intervals.bisect((left, right))
  11.         # consider left one
  12.         if self.intervals[i - 1][1] >= left:
  13.             i -= 1
  14.             left = self.intervals[i][0]
  15.         # right overlap
  16.         while i < len(self.intervals) and self.intervals[i][0] <= right:
  17.             l, r = self.intervals.pop(i)
  18.             right = max(right, r)
  19.             self.cnt -= r - l + 1
  21.         self.intervals.add((left, right))
  22.         self.cnt += right - left + 1
  24.     def count(self) -> int:
  25.         return self.cnt

注意的几个点：

  • 边界值的判断，index判断，或者采用解答中的添加guard值
  • 涉及删除操作（pop)时，考虑遍历时发生的变化
  • 考虑左右处理的先后，会不会互相影响