1109. Corporate Flight Bookings¶
题目信息¶
- 题号:
1109
- 难度:
Medium
- 主题:
差分数组、区间累加、航班预订
- 原题:
- 重点:
每条记录把座位数累加到从
first到last的所有航班;航班编号从1开始且区间两端都包含
题目重述¶
共有 n 个航班,编号为 1 到 n。每条预订 bookings[i] = [first_i, last_i, seats_i] 表示从 first_i 到 last_i 的每个航班都新增 seats_i 个预订座位。
多条预订会累加。请返回长度为 n 的数组,其中第 j 项表示编号 j + 1 的航班最终预订座位总数。
1 <= bookings.length <= 2 * 10^4,1 <= first_i <= last_i <= n <= 2 * 10^4,1 <= seats_i <= 10^4。
自建示例¶
多个闭区间在中间航班重叠:
输入:bookings = [[1,2,10],[2,4,5],[4,4,7]], n = 5
输出:[10,15,5,12,0]
解释:第二个航班获得前两条预订共 15 个座位;第四个航班获得后两条预订共 12 个座位;第五个航班没有预订。
只有一个航班:
输入:bookings = [[1,1,9]], n = 1
输出:[9]
解释:唯一预订区间只覆盖唯一航班,因此结果为 9。