描述

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

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

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

• https://leetcode-cn.com/problems/corporate-flight-bookings/

思路

差分数组,注意差分数组的变化的临界值判断。

CODE

• Time Limit Exceeded

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        # 结果初始化
        result = []
        for i in range(n):
            result.append(0)


        for m in range(bookings.__len__()):
            diff = self.diffList(result,bookings[m][0],bookings[m][1],bookings[m][2])

            result[0] = diff[0]
            for n in range(len(result) - 1):
                result[n + 1] = result[n] + diff[n+1]

        return result

    # 差分数组更新方法
    # m 对应dif 的 m - 1
    def diffList(self,inputList,m,n,add):

        # 差分数组构造
        dif = [inputList[0]]
        for i in range(len(inputList) - 1):
            dif.append(inputList[i+1] - inputList[i])

        dif[m - 1] += add

        if n != len(inputList):
            dif[n] -= add

        return dif        

• Accept

先创建所有改变结果的差分数组，最后再递推结果。再原基础上进行构造差分数组，优化了存储空间。

class Solution4:
    def corpFlightBookings(self, bookings, n):
        # 创造一个初始结果list
        f = [0 for _ in range(n)]
        print(f)

        for s, e, diff in bookings:
            print("s " + str(s) + "\te " + str(e) + "\tdiff " + str(diff))
            # 这里是为了我们常规理解的位置和list位置相对应
            s -= 1
            e -= 1

            # 差分数组只更改了区间端口的两个值
            # 先构造了完整的差分数组
            # 没有新建，在原值上进行了更新，优化了存储空间
            # 谁说了差分数组只能新建一个的？新建可能容易理解一些
            # 开始改变的端口
            f[s] += diff
            # 这里是为了避免改变有可能到最后一个也需要改变的情况
            if e + 1 < n:
                # 撤销改变
                f[e + 1] -= diff
            print(f)
            print("------------------------------------------")

        # 再用差分数组对结果值进行反推
        for i in range(1, n):
            print(i)
            print(f)
            f[i] += f[i - 1]
            print('-------------------')
        return f

S4 = Solution4()
booking = [[1,2,10],[2,3,20],[2,5,25],[5,5,15],[2,2,3]]
n = 5
result = str(S4.corpFlightBookings(booking,n))
print("##################################")
print(result)