1109. 航班预订统计
#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 | 输入:bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5 |
示例 2:
1 | 输入:bookings = [[1,2,10],[2,2,15]], n = 2 |
提示:
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 | var corpFlightBookings = function (bookings, n) { |
但是时间只超过了50%,就考虑问题
问题应该在O^2的复杂度上
后来想遍历的时候
- Array(n).fill(0) 代码更优美
- 把增量加在数组里,最后走for循环跑一次就可以降一层for循环
1 | const [first, last, seats] = item; |