题目
这里有 n 个航班，它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer，其中 answer[i] 是航班 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 bookings[i].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，这样数据就完全正确了
文字可能说有点啰嗦，但是思路已经讲的很通熟易懂了 参考leetcode-cn.com/problems/co…
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)
