差分数组合并区间

给你一个下标从 0 开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 i，nums[i] = [starti, endi] ，其中 starti 是第 i 辆车的起点，endi 是第 i 辆车的终点。

返回数轴上被车 任意部分 覆盖的整数点的数目。

示例 1：

输入：nums = [[3,6],[1,5],[4,7]]
输出：7
解释：从 1 到 7 的所有点都至少与一辆车相交，因此答案为 7 。

示例 2：

输入：nums = [[1,3],[5,8]]
输出：7
解释：1、2、3、5、6、7、8 共计 7 个点满足至少与一辆车相交，因此答案为 7 。

在方法一中，对于每一辆汽车我们都需要 O(C) 的时间更新数组count。注意到我们一定是对数组 count 的连续一段增加一个相同的值 1，因此可以使用差分的思想优化时间复杂度。

具体地，我们令数组 diff 中的每个元素是数组 count 中相邻两个元素的差值，即：

diff[i]={count[i],count[i]−count[i−1],ifi=0ifi>0

如果我们维护数组 diff，那么 count[i] 可以通过从 diff[0] 累加到 diff[i] 方便地求出。

当我们需要将数组 count 中下标从 x 到 y 的元素均增加 1 时，对应到数组 diff，只需要将 diff[x] 增加 1，并将 diff[y+1] 减少 1，时间复杂度从 O(C) 降低至 O(1)。

最后只需要对数组 diff 求一遍前缀和，就还原出了数组 count，其中非零元素的数量即为答案。

func numberOfPoints(nums [][]int) int {
    C := 0
  for _, interval := range nums {
    if interval[1] > C {
      C = interval[1]
    }
  }

  diff := make([]int, C + 2)
  for _, interval := range nums {
    diff[interval[0]]++
    diff[interval[1] + 1]--
  }

  ans, count := 0, 0
  for i := 1; i <= C; i++ {
    count += diff[i]
    if count > 0 {
      ans++
    }
  }

  return ans
}