LeetCode 1109. 航班预订统计
原创
题目
这里有 n 个航班，它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings ，表中第 i 条预订记录 bookingsi = firsti, lasti, seatsi 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer，其中 answeri 是航班 i 上预订的座位总数。
示例 1：
输入：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]
示例 2：
输入：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
bookingsi.length == 3
1 <= firsti <= lasti <= n
1 <= seatsi <= 104
解题思路
把每条预定记录的起始航班i记录为k个座位，终点航班j+1记录为-k个座位
为什么要把终点航班j+1记录为-k个座位呢，那i至j之间的航班就不记录了吗？
我们设想下，当只有一条预定记录的时候bookings=[2,5,25]（随便假设的数据）
这时候航班的座位数就是0,25,0,0,0,-25,这时候再用一个for循环
n = 5 # 5个航班a = [0,25,0,0,0,-25]for i in range(n): a[i+1] += a[i]是不是数据就变成了0,25,25,25,25,0了，到这里，初步的思路已经有了，那么当bookings有很多
预定记录的时候，我们就可以先构造0,25,0,0,0,-25这样的一种数据,例如题目的例子
bookings = [1,2,10,2,3,20,2,5,25], n = 5
构造出来的航班数据是10,45,-10,-20,0,-25，拆分出来解释就是3条数据10,0,-10,0,0,0,0,20,0,-20,0,0,0,25,0,0,0,-25
这时候，再用for循环的话。从10开始加到第2航班，10+45=55，当10加到第三航班的时候，因为1,2,10的1，2航班才是有10个座位，
所以10+(-10),就消除了10个座位，后面的数据也是同样的道理，当航班超过了i,j,k的i和j的话，就会有相对应的-k来消除k，这样数据就完全正确了
文字可能说有点啰嗦，但是思路已经讲的很通熟易懂了
class Solution:
def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
# ##暴力解法，超时
# answerList = [0]*n
# for nList in bookings:
# first = nList[0]-1
# last = nList[1]
# seats = nList[2]
# for i in range(first, last):
# answerList[i] += seats
# return answerList
## 差分数组
answerList = [0]*n
for first, last, seats in bookings:
answerList[first-1] += seats
if last < n:
answerList[last] += -seats
# print(answerList)
for i in range(1, n):
answerList[i] += answerList[i-1]
return answerList
if __name__ == '__main__':
bookings = [[1,2,10],[2,3,20],[2,5,25]]
n = 5
ret = Solution().corpFlightBookings(bookings, n)
print(ret)原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
