LeetCode 1109. 航班预订统计

题目

这里有 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，这样数据就完全正确了

文字可能说有点啰嗦，但是思路已经讲的很通熟易懂了
参考https://leetcode-cn.com/problems/corporate-flight-bookings/solution/kan-bu-dong-jiu-lai-kan-wo-by-hjj-11/

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)