目录

题目来源

题目描述

示例

提示

题目解析

算法源码

题目来源

1109. 航班预订统计 - 力扣（LeetCode）

题目描述

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

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

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

示例

提示

1 <= n <= 2 * 104
1 <= bookings.length <= 2 * 104
bookings[i].length == 3
1 <= firsti <= lasti <= n
1 <= seatsi <= 104

题目解析

本题如果用暴力求解的话，即双重for，外层遍历bookings，内层遍历bookings[i]，

bookings[i][0]代表一个起始航班，bookings[i][1]代表一个终点航班，bookings[i][2]代表一个航班预定座位数

预先定义一个航班座位数组arr，arr[k]表示k航班预定的座位数。

在内层遍历中，再定义一个for循环，遍历bookings[i][0]~bookings[i][1]的每一个航班k，给对应的arr[k] += bookings[i][2]即可。

这个算法时间复杂度是 O(n^3)，在本题数量级来看是超时的。

而本题其实是典型的为给定区间所有元素加上一个增量，可以利用差分数列求解。关于差分数列，请看：

算法设计 - 前缀和 & 差分数列_伏城之外的博客-CSDN博客

Java算法源码

class Solution {public int[] corpFlightBookings(int[][] bookings, int n) {int[] diff = new int[n];for(int i=0; i