1109.航班预订统计

一、问题描述

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

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

请你返回一个长度为 n 的数组 answer，其中 answer[i] 是航班 i 上预订的座位总数。

示例:

输入：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]

二、方案一：直接更新

1、思路

最直接的方法是按照给定的预订记录直接更新数组。对于每条预订记录，我们遍历指定区间并增加相应的座位数。

2、代码实现

func corpFlightBookings(bookings [][]int, n int) []int {
    result := make([]int, n)
    for _, booking := range bookings {
        first, last, seats := booking[0]-1, booking[1]-1, booking[2]
        for i := first; i <= last; i++ {
            result[i] += seats
        }
    }
    return result
}

3、复杂度分析

• 时间复杂度：O(n*k)，其中 n 是数组的长度，k 是预订记录的数量。在最坏的情况下，我们需要对数组中的每个元素进行更新。
• 空间复杂度：O(1)，不需要额外的空间。

三、方案二：差分数组

1、思路

与之前的题目类似，我们可以使用差分数组来处理区间更新问题。创建一个差分数组 diff，其中 diff[i] 表示数组 result 中下标 i 和 i-1 之间的差值（result[i] - result[i-1]）。通过更新差分数组，我们可以快速地更新原数组。

对于每条预订记录 [first, last, seats]，我们在差分数组 diff 的 first 处增加 seats，并在 last + 1 处减少 seats。最后，我们通过差分数组来重建原数组。

2、代码实现

func corpFlightBookings(bookings [][]int, n int) []int {
	// 差分数组
	nums := make([]int, n)
	for _, booking := range bookings {
		start, end, inc := booking[0], booking[1], booking[2]
		// 差分数组 d[l−1] 增加 inc
		nums[start-1] += inc
		if end < n {
			// 差分数组 d[r] 减少 inc
			nums[end] -= inc
		}
	}
	// 对差分数组求前缀和得到原数组
	for i := 1; i < n; i++ {
		nums[i] += nums[i-1]
	}

	return nums
}

3、复杂度分析

• 时间复杂度：O(n+k)，其中 n 是数组的长度，k 是预订记录的数量。我们需要遍历每个预订记录并更新差分数组，然后遍历差分数组来重建原数组。
• 空间复杂度：O(n)，我们需要一个长度为 n 的差分数组。

四、总结

方案	时间复杂度	空间复杂度
直接更新	O(n*k)	O(1)
差分数组	O(n+k)	O(n)

差分数组方法在处理大量区间更新操作时更加高效，尤其是当更新操作的数量远大于数组长度时。