1109. Corporate Flight Bookings

题目信息

题号:

1109

难度:

Medium

主题:

差分数组、区间累加、航班预订

原题:

LeetCode 1109

重点:

每条记录把座位数累加到从 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。