There are n flights, and they are labeled from 1 to n.
We have a list of flight bookings. The i-th booking bookings[i] = [i, j, k] means that we booked k seats from flights labeled i to j inclusive.
Return an array answer of length n, representing the number of seats booked on each flight in order of their label.
Example 1:
Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5 Output: [10,55,45,25,25]
Constraints:
1 <= bookings.length <= 200001 <= bookings[i][0] <= bookings[i][1] <= n <= 200001 <= bookings[i][2] <= 10000
航班预订统计。题意是给一个叫做bookings的二维数组，里面包含了一些[i, j, k]的子数组，分别表示一些航班的预订情况，从i到j航班，有K个预订。同时给了一个变量N表示航班的数量。请输出一个数组表示所有航班的预订情况。
这里我给出两种方法。首先是暴力解。对于每一个booking，因为给了起始航班i，结束航班j和人数k，所以对于[i, j]这些航班，我们对res[i]累加k即可。注意最后结果集里面下标是不包含0的，所以需要重新写一份。
时间O(n^2) - worst case
空间O(n)
Java实现
1 class Solution {
2 public int[] corpFlightBookings(int[][] bookings, int n) {
3 int[] temp = new int[n + 1];
4 for (int[] book : bookings) {
5 int start = book[0];
6 int end = book[1];
7 int seat = book[2];
8 for (int i = start; i <= end; i++) {
9 temp[i] += seat;
10 }
11 }
12 int[] res = new int[n];
13 for (int i = 1; i < temp.length; i++) {
14 res[i - 1] = temp[i];
15 }
16 return res;
17 }
18 }
其次是一个类似扫描线的方法。当你拿到一个booking = [i, j, k]的时候，意味着在[0, i)和(j, n]这些航班，是没有这些乘客的。对于第i个航班来说，他比第i - 1个航班要多k个乘客；然后对于j之后的航班，他们又失去了这些乘客。所以我们可以创建一个counter数组，用累加的方式记录航班之间的乘客数量的变化。
遍历每个booking（b），在counter[b[0] - 1]上 += b[2]，说明从第b[0]个航班，突然比之前所有的航班都多了k个乘客；同时如果b[1] < n（b[1]的下标不能越界），在counter[b[1]] -= b[2]，说明从b[1]个航班开始，突然比之前所有的航班都少了k个乘客。
时间O(n)
空间O(n)
Java实现
1 class Solution {
2 public int[] corpFlightBookings(int[][] bookings, int n) {
3 int[] counters = new int[n];
4 for (int[] b : bookings) {
5 counters[b[0] - 1] += b[2];
6 if (b[1] < n) {
7 counters[b[1]] -= b[2];
8 }
9 }
10 for (int i = 1; i < n; i++) {
11 counters[i] += counters[i - 1];
12 }
13 return counters;
14 }
15 }
相关题目
1109. Corporate Flight Bookings