2848-与车相交的点

给你一个下标从 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 。

提示：

• 1 <= nums.length <= 100
• nums[i].length == 2
• 1 <= starti <= endi <= 100

视频讲解 。

假设我们有一个数组，对于示例 1，我们可以把下标在 [3,6] 的元素都加一，把下标在 [1,5] 的元素都加一，下标在 [4,7] 的元素都加一。

然后，我们来看看有多少个下标对应的元素值是大于 0 的，这些下标就是题目要计算的，被任意区间覆盖的整数点。

那么，如何快速地「把区间内的数都加一」呢？

我之前在力扣上写过一篇文章：【算法小课堂】差分数组 。

根据这篇文章，用差分数组 diff 快速完成区间操作，然后求它的前缀和（恢复原数组），统计前缀和中有多少个数大于 0，即为答案。

[sol-Python3]

class Solution:
    def numberOfPoints(self, nums: List[List[int]]) -> int:
        max_end = max(end for _, end in nums)
        diff = [0] * (max_end + 2)
        for start, end in nums:
            diff[start] += 1
            diff[end + 1] -= 1
        return sum(s > 0 for s in accumulate(diff))

[sol-Java]

class Solution {
    public int numberOfPoints(List<List<Integer>> nums) {
        var diff = new int[102];
        for (var p : nums) {
            diff[p.get(0)]++;
            diff[p.get(1) + 1]--;
        }
        int ans = 0, s = 0;
        for (int d : diff) {
            s += d;
            if (s > 0) {
                ans++;
            }
        }
        return ans;
    }
}

[sol-C++]

class Solution {
public:
    int numberOfPoints(vector<vector<int>> &nums) {
        int diff[102]{};
        for (auto &p: nums) {
            diff[p[0]]++;
            diff[p[1] + 1]--;
        }
        int ans = 0, s = 0;
        for (int d: diff) {
            s += d;
            ans += s > 0;
        }
        return ans;
    }
};

[sol-Go]

func numberOfPoints(nums [][]int) (ans int) {
	diff := [102]int{}
	for _, p := range nums {
		diff[p[0]]++
		diff[p[1]+1]--
	}
	s := 0
	for _, d := range diff {
		s += d
		if s > 0 {
			ans++
		}
	}
	return
}

[sol-JavaScript]

var numberOfPoints = function(nums) {
    const diff = new Array(102).fill(0);
    for (const p of nums) {
        diff[p[0]]++;
        diff[p[1] + 1]--;
    }
    let ans = 0, s = 0;
    for (const d of diff) {
        s += d;
        ans += s > 0;
    }
    return ans;
};

复杂度分析

• 时间复杂度：\mathcal{O}(n+\max{\textit{end}_i})。其中 n 为 nums 的长度。
• 空间复杂度：\mathcal{O}(\max{\textit{end}_i})。

相似题目

请看【算法小课堂】差分数组 中的题单。