0%

1109. 航班预订统计

#Leetcode-1109. 航班预订统计

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

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

有一份航班预订表 bookings ,表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firstilasti包含 firstilasti )的 每个航班 上预订了 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;