1109. 航班预订统计【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 差分数组

1. 📝 题目描述

• leetcode

这里有 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 * 10^4
• 1 <= bookings.length <= 2 * 10^4
• bookings[i].length == 3
• 1 <= firsti <= lasti <= n
• 1 <= seatsi <= 10^4

2. 🎯 s.1 - 差分数组

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[][]} bookings
 * @param {number} n
 * @return {number[]}
 */
var corpFlightBookings = function (bookings, n) {
  const diff = new Array(n + 2).fill(0)
  for (const [first, last, seats] of bookings) {
    diff[first] += seats
    diff[last + 1] -= seats
  }
  const res = new Array(n)
  res[0] = diff[1]
  for (let i = 1; i < n; i++) {
    res[i] = res[i - 1] + diff[i + 1]
  }
  return res
}

• 时间复杂度：$O(m+n)$，其中 $m$ 是 bookings 的长度
• 空间复杂度：$O(n)$，差分数组的开销

算法思路：

• 建立差分数组，对每条预订记录在 first 处加上 seats，在 last+1 处减去 seats
• 前缀和还原得到每个航班的实际预订总数