image.png

思路一-差分数组

  • 当数据量比较大的时候,如果每次遍历区间内部的点,则时间复杂度会过高。因此试图维护一个答案之外更丰富的信息。
  • 使用一个差分数组记录每个点之间覆盖次数的差值。这样最后通过从前到后遍历,累加,即可得到某个点的覆盖次数,那些被覆盖0次的即为答案。

    思路二-区间合并问题

增大数据-离散化

image.png
image.png

  • 依然可以对每个端点记录差分值,只是不用记载整个数组。
  • 根据数组的第一个元素进行排序。