LeetCode-1109-航班预定统计

目录

题目来源

题目描述

示例

提示

题目解析

算法源码

---

题目来源

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

题目描述

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

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

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

示例 输入bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5输出[10,55,45,25,25]说明航班编号        1   2   3   4   5 预订记录 1 ：   10  10 预订记录 2 ：       20  20 预订记录 3 ：       25  25  25  25 总座位数：      10  55  45  25  25 因此，answer = [10,55,45,25,25] 输入bookings = [[1,2,10],[2,2,15]], n = 2输出[10,25]说明航班编号        1   2 预订记录 1 ：   10  10 预订记录 2 ：       15 总座位数：      10  25 因此，answer = [10,25] 提示

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<bookings.length; i++) { int start = bookings[i][0]; int end = bookings[i][1]; int add = bookings[i][2]; diff[start - 1] += add; if(end < n) diff[end] -= add; } int[] ans = new int[n]; ans[0] = diff[0]; for(int i=1; i<n; i++) { ans[i] = ans[i-1] + diff[i]; } return ans; } }