题目描述
思路
暴力算法模拟
前缀和
代码

leetcode - daily - 1109. 航班预订统计

题目描述

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

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

请你返回一个长度为 n 的数组 answer,其中 answer[i] 是航班 i 上预订的座位总数。

 

示例 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


来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/corporate-flight-bookings
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

暴力算法模拟

/**
 * @param {number[][]} bookings
 * @param {number} n
 * @return {number[]}
 */
var corpFlightBookings = function (bookings, n) {
  let ans = Array.from({ length: n }).fill(0);

  for (let [start, end, count] of bookings) {
    for (let i = start - 1; i < end; i++) {
      ans[i] += count;
    }
  }

  return ans;
};
  • 时间复杂度: $O(N * M)$, N 为航班数, M 为预定数
  • 空间复杂度: $O(N)$

前缀和

对每一个预定 [start, end, count], 在航班 start 会上 count 个人, 在航班 end 上会下 count 个人, 那么在第 i 趟航班上的人数 people[i] 为前 i 趟航班每次上的人总和,这个可以通过前缀和计算

令 seats[i] 为第 i 趟航班预定的位置数量, people[i] 为第 i 趟航班飞机上人数,根据前缀和有

people[i] = people[i - 1] + seats[i]

所以问题关键在与计算 seats[i], 也就是在第 i 趟航班新增的人数, 由于每一个预定 [start, end, count] 在 start 上飞机, end 下飞机。因此对每一个预定 [start, end, count], seats 可以通过以下方式计算

seats[start] += count
seats[end] -= count

代码

var corpFlightBookings = function (bookings, n) {
  let seats = Array.from({ length: n }).fill(0);

  // 计算每个航班新增的seat数 (ps: 可正可负)
  for (let [start, end, seat] of bookings) {
    seats[start - 1] += seat;
    if (end < n) {
      seats[end] -= seat;
    }
  }

  // 前缀和
  for (let i = 0; i < n - 1; i++) {
    seats[i + 1] += seats[i];
  }
  return seats;
};
  • 时间复杂度: $O(M)$, M 为预定记录数
  • 空间复杂度: $O(N)$, N 为航班数

feiker 少年起而行之