1109. 航班预订统计

Posted on Edited on In

#Leetcode-1109. 航班预订统计

难度中等157收藏分享切换为英文接收动态反馈

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

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

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

示例 1：

1
2
3
4
5
6
7
8
9
输入：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：

1
2
3
4
5
6
7
8
输入：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

Solution

题目到是很简单，主要做的就是一维数组做个累加，时间复杂度O(N^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
var corpFlightBookings = function (bookings, n) {
  const answer = [];
  for (let i = 0; i < n; i++)answer.push(0);
  for (let item of bookings) {
    const [first, last, seats] = item;
    for (let j = first; j <= last; j++) {
      answer[j-1] += seats;
    }
  }
  return answer;

};
console.log(corpFlightBookings([[1, 2, 10], [2, 3, 20], [2, 5, 25]], 5))

但是时间只超过了50%，就考虑问题

问题应该在O^2的复杂度上

后来想遍历的时候

  • Array(n).fill(0) 代码更优美
  • 把增量加在数组里，最后走for循环跑一次就可以降一层for循环
1
2
3
const [first, last, seats] = item;
answer[first - 1] += seats;
if (last < n) answer[last] -= seats;