What is the key pattern in Corporate Flight Bookings?

The core pattern is difference array plus prefix sum. Each booking updates only the start and end boundary, and one running sum pass converts those markers into the final seat totals for every flight.

Why is the brute force solution too slow for this problem?

Because one booking can cover many flights, a direct loop from first to last for every booking repeats work across overlapping ranges. In the worst case, Corporate Flight Bookings becomes much slower than necessary when many intervals are long.

Why do we subtract at last instead of last - 1 in the optimized solution?

The booking range is inclusive, so the added seats must still apply to flight last. Subtracting at index last in 0-based storage means the running total stops only after that flight has been counted.

How does the sample produce [10,55,45,25,25]?

Booking [1,2,10] adds 10 to flights 1 and 2, booking [2,3,20] adds 20 to flights 2 and 3, and booking [2,5,25] adds 25 to flights 2 through 5. Summing per flight gives 10, 55, 45, 25, and 25.

Is prefix sum alone enough without a difference array?

Not for efficient updates in this problem. Prefix sum is the reconstruction step, but the real speedup in Corporate Flight Bookings comes from first storing each booking as boundary changes instead of updating every covered flight immediately.

#1109

Medium

auto_awesome前缀和

LeetCode 题解工作台

航班预订统计

这里有 n 个航班，它们分别从 1 到 n 进行编号。有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [first i , last i , seats i ] 意味着在从 first i 到 last i （包含 first i 和 last i ）的…

数组前缀和

题目描述

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

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

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

示例 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 * 10⁴
1 <= bookings.length <= 2 * 10⁴
bookings[i].length == 3
1 <= first_i <= last_i <= n
1 <= seats_i <= 10⁴

lightbulb

解题思路

方法一：差分数组

我们注意到，每一次预订都是在某个区间 [first, last] 内的所有航班上预订了 seats 个座位。因此，我们可以利用差分数组的思想，对于每一次预订，将 first 位置的数加上 seats，将 last + 1 位置的数减去 seats。最后，对差分数组求前缀和，即可得到每个航班预定的座位总数。

时间复杂度 $O(n)$ ，其中 $n$ 为航班数。忽略答案的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        ans = [0] * n
        for first, last, seats in bookings:
            ans[first - 1] += seats
            if last < n:
                ans[last] -= seats
        return list(accumulate(ans))

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The interviewer emphasizes inclusive ranges, which usually hints that you should mark start and stop points instead of updating every flight directly.
question_mark
They ask whether you can do better than touching every index inside each booking range, pointing toward a difference array optimization.
question_mark
They care about overlapping bookings and final per-flight totals, which is a strong signal for range updates followed by a prefix sum rebuild.

warning

常见陷阱

外企场景

error
Forgetting the 1-based flight labels and writing updates as if the array were already 0-based, which shifts every reservation.
error
Subtracting at last - 1 instead of last when ending a booking range, which breaks the inclusive boundary for Corporate Flight Bookings.
error
Trying to prefix-sum before all booking markers are placed, which mixes partial state with final totals and hides boundary bugs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the maximum reserved seats on any single flight after processing all bookings, which still comes from the same rebuilt prefix array.
arrow_right_alt
Support cancellation records with negative seat values, where the same difference array pattern still works as long as updates are applied correctly.
arrow_right_alt
Answer seat totals after each incremental booking batch, which may push the discussion toward repeated prefix rebuilds or a more dynamic range update structure.

help

常见问题

外企场景

继续练习

#1094 拼车 #1124 表现良好的最长时间段 #1140 石子游戏 II