1109. 航班预订统计

yzhms

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

我们这儿有一份航班预订表，表中第 i 条预订记录 bookings = [i, j, k] 意味着我们在从 i 到 j 的每个航班上预订了 k 个座位。

请你返回一个长度为 n 的数组 answer，按航班编号顺序返回每个航班上预订的座位数。



示例：

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]


提示：

1 <= bookings.length <= 20000
1 <= bookings[0] <= bookings[1] <= n <= 20000
1 <= bookings[2] <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/corporate-flight-bookings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

yzhms

航班预定---公交车模型
gpking 发布于 8 天前

此题按照自己的想法按照输入每次通过下标叠加到对应的航班次数。但是这样问题的时间复杂度为O(n*m)。在该题中只能通过一部分用例。

参照题解了解到了公交车上下的这种模型。

因为航班可以看做一系列的站台，公交车从第0个站台启动，每个站台有上有下，最终可以根据每站的上下确定出每站的乘客数量。

比如站台0上车4人，站台1下车2人，上车3人，这样站台1的变更数量就是1,此时车上的总人数是5人：4 + 1。

航班预定场景中：航线i和航线j增加了K个乘客。实际可以认为在航班i上车了K个乘客，乘坐到了j站台之后下车，即站台j+1处下车，-K个乘客。通过统计每个站台的上下人数和上一个站台的人员信息就能确定出整个航线的预定信息。

1. /**
   
2. * Note: The returned array must be malloced, assume caller calls free().
   
3. */
   
4. #define MAX_CNT 20000
   
5. int* corpFlightBookings(int** bookings, int bookingsSize, int* bookingsColSize, int n, int* returnSize) {
   
6.     int *result;
   
7.     int *p;
   
8.     int i, j;
   
9.     if (!bookings || !bookingsSize || !bookingsColSize || !returnSize || !bookings[0]) {
   
10.         if (returnSize) {
    
11.             *returnSize = 0;
    
12.         }
    
13.         return NULL;
    
14.     }
    
15.     //printf("bookingsSize=%d, bookingsColSize=%d, n=%d\n", bookingsSize, *bookingsColSize, n);
    
16.     result = (int*)malloc(sizeof(int) * n);
    
17.     p = (int*)malloc(sizeof(int) * n);
    
18.     memset(result, 0, sizeof(int) * n);
    
19.     memset(p, 0, sizeof(int) * n);
    
20. 
    
21.     for (i = 0; i < bookingsSize; i++) {
    
22.         p[bookings[i][0] - 1] += bookings[i][2];
    
23.         if (bookings[i][1] < n) {
    
24.             p[bookings[i][1]] -= bookings[i][2];
    
25.         }
    
26.     }
    
27.     result[0] = p[0];
    
28.     for (i = 1; i < n; i++) {
    
29.         result[i] = result[i - 1] + p[i];
    
30.     }
    
31.     *returnSize = n;
    
32.     //printf("returnSize=%d\n", *returnSize);
    
33.     return result;
    
34. }

复制代码

执行结果：通过
显示详情

执行用时 :348 ms, 在所有 C 提交中击败了92.11%的用户
内存消耗 :33.8 MB, 在所有 C 提交中击败了100.00%的用户