<p>You are given a <strong>0-indexed</strong> 2D integer array <code>nums</code> representing the coordinates of the cars parking on a number line. For any index <code>i</code>, <code>nums[i] = [start<sub>i</sub>, end<sub>i</sub>]</code> where <code>start<sub>i</sub></code> is the starting point of the <code>i<sup>th</sup></code> car and <code>end<sub>i</sub></code> is the ending point of the <code>i<sup>th</sup></code> car.</p>

<p>Return <em>the number of integer points on the line that are covered with <strong>any part</strong> of a car.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [[3,6],[1,5],[4,7]]
<strong>Output:</strong> 7
<strong>Explanation:</strong> All the points from 1 to 7 intersect at least one car, therefore the answer would be 7.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [[1,3],[5,8]]
<strong>Output:</strong> 7
<strong>Explanation:</strong> Points intersecting at least one car are 1, 2, 3, 5, 6, 7, 8. There are a total of 7 points, therefore the answer would be 7.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 100</code></li>
	<li><code>nums[i].length == 2</code></li>
	<li><code><font face="monospace">1 &lt;= start<sub>i</sub>&nbsp;&lt;= end<sub>i</sub>&nbsp;&lt;= 100</font></code></li>
</ul>

'''
差分数组的原理
假设我们有一个数组 arr，初始值全为 0。我们希望对数组中的某些区间进行加减操作。
例如，对区间 [start, end] 进行加 1 操作。
直接更新：
直接更新需要遍历区间内的每个元素，逐个加上 1。这种方式的时间复杂度是 O(n)，其中 n 是区间的长度。

差分数组：
差分数组 diff 记录的是每个位置的变化量。具体来说：
diff[start] += 1：表示从 start 开始，每个元素的值增加 1。
diff[end + 1] -= 1：表示从 end + 1 开始，每个元素的值减少 1。
这样，我们只需要在 start 和 end + 1 这两个位置进行操作，时间复杂度是 O(1)。

差分数组的累加
通过差分数组，我们可以通过累加来恢复原始数组的值。

时间复杂度：O(n+U)。其中 n 为 nums 的长度，U=max{end}。
空间复杂度：O(U)。
'''
class Solution:
    def numberOfPoints(self, nums: List[List[int]]) -> int:
        # 找到所有区间中最大的结束点 end，并将其存储在 max_end 变量中
        max_end = max(end for _, end in nums)

        # 长度为 max_end + 2 的列表，初始化为全零。这个列表用于记录每个点的覆盖情况的变化
        # max_end + 2 是因为需要处理 end + 1 的情况，所以数组长度需要比最大结束点大 2
        diff = [0] * (max_end + 2)

        # 对每个区间 [start, end]，在 start 位置增加 1，在 end + 1 位置减少 1
        for start, end in nums:
            diff[start] += 1
            diff[end + 1] -= 1
        
        # accumulate(diff) 对 diff 数组进行累加，得到每个点的实际覆盖次数
        # sum(s > 0 for s in accumulate(diff)) 统计累加结果中大于 0 的元素个数，即被覆盖的点的总数
        return sum(s > 0 for s in accumulate(diff))
16300