航班预订统计

标签: 数组 前缀和

难度: Medium

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

示例 1：

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25
因此，answer = [10,55,45,25,25]

示例 2：

输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号        1   2
预订记录 1 ：   10  10
预订记录 2 ：       15
总座位数：      10  25
因此，answer = [10,25]

提示：

  • 1 <= n <= 2 * 104
  • 1 <= bookings.length <= 2 * 104
  • bookings[i].length == 3
  • 1 <= firsti <= lasti <= n
  • 1 <= seatsi <= 104

Submission

运行时间: 46 ms

内存: 27.1 MB

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        nums = [0] * n
        for l, r, x in bookings:
            nums[l - 1] += x
            if r < n:
                nums[r] -= x
        return list(itertools.accumulate(nums))

Explain

题解使用了差分数组的技巧来解决航班预订统计的问题。首先初始化一个长度为n的数组nums，所有元素初始值为0。对于每条预订记录[l, r, x]，在nums的l-1位置加上x（代表从第l个航班开始增加x个座位），并在r位置减去x（代表第r+1个航班开始减少x个座位，这样就不会影响第r个航班）。这样设置后，nums数组的每个位置仅表示从当前位置开始的增量变化。最后，使用累积和函数itertools.accumulate对nums进行处理，得到每个航班的总座位数。

时间复杂度: O(m + n)

空间复杂度: O(n)

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        nums = [0] * n  # 初始化差分数组
        for l, r, x in bookings:  # 遍历所有预订记录
            nums[l - 1] += x  # 在起始航班位置增加座位数
            if r < n:  # 如果结束航班不是最后一个航班，则在结束航班的下一个位置减去座位数
                nums[r] -= x
        return list(itertools.accumulate(nums))  # 计算从第1个航班到每个航班的累积座位数

Explore

在差分数组中，我们增加x到l-1位置以增加从第l个航班开始的座位数。为了确保这个增加只影响到第r个航班，我们需要在第r个航班之后的位置（即r位置，因为数组索引从0开始）减去x。这样操作后，累积和计算时，从第r+1个航班开始，增加的座位数就会被抵消，不影响第r+1个及之后的航班。如果在r+1位置操作，将会导致第r个航班的座位数没有被正确减少。

差分数组的方法主要优势在于效率。使用差分数组只需要对每个预订操作进行常数时间的更新（即在l-1和r位置各一次操作），然后使用一次线性时间的累积和计算来获取最终结果。总体时间复杂度是O(n + k)，其中k是预订记录数量，n是航班数量。相比之下，如果直接遍历bookings数组更新每个航班的座位数，则每个预订可能需要O(n)的时间来更新航班座位，对所有预订操作复杂度可能达到O(k*n)，在k和n都较大时效率会显著降低。

如果预订记录中的firsti为1，即预订从第一个航班开始，则在差分数组nums中，我们会在0索引位置（即第一个航班）增加座位数。由于没有更早的航班，因此不需要在负索引位置操作，只需要保证在结束航班后正确减少座位数即可。这是因为差分数组的设计自然适应了从数组第一个位置开始的变化。

差分数组记录的是从一个航班到下一个航班的座位数变化量。通过对这些变化量进行累积求和，可以有效地构建出每一个航班的实际座位数。累积和的结果是从第一个航班开始，逐步加上每个航班的变化量，因此能够准确地反映每一个航班在所有预订操作后的总座位数。这是一种将局部修改信息整合为全局视图的高效方法。