Welcome to Subscribe On Youtube
1109. Corporate Flight Bookings
Description
There are n
flights that are labeled from 1
to n
.
You are given an array of flight bookings bookings
, where bookings[i] = [first_{i}, last_{i}, seats_{i}]
represents a booking for flights first_{i}
through last_{i}
(inclusive) with seats_{i}
seats reserved for each flight in the range.
Return an array answer
of length n
, where answer[i]
is the total number of seats reserved for flight i
.
Example 1:
Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5 Output: [10,55,45,25,25] Explanation: Flight labels: 1 2 3 4 5 Booking 1 reserved: 10 10 Booking 2 reserved: 20 20 Booking 3 reserved: 25 25 25 25 Total seats: 10 55 45 25 25 Hence, answer = [10,55,45,25,25]
Example 2:
Input: bookings = [[1,2,10],[2,2,15]], n = 2 Output: [10,25] Explanation: Flight labels: 1 2 Booking 1 reserved: 10 10 Booking 2 reserved: 15 Total seats: 10 25 Hence, answer = [10,25]
Constraints:
1 <= n <= 2 * 10^{4}
1 <= bookings.length <= 2 * 10^{4}
bookings[i].length == 3
1 <= first_{i} <= last_{i} <= n
1 <= seats_{i} <= 10^{4}
Solutions
Solution 1: Difference Array
We notice that each booking is for seats
seats on all flights within a certain interval [first, last]
. Therefore, we can use the idea of a difference array. For each booking, we add seats
to the number at the first
position and subtract seats
from the number at the last + 1
position. Finally, we calculate the prefix sum of the difference array to get the total number of seats booked for each flight.
The time complexity is $O(n)$, where $n$ is the number of flights. Ignoring the space consumption of the answer, the space complexity is $O(1)$.
Solution 2: Binary Indexed Tree + Difference Idea
We can also use a binary indexed tree, combined with the idea of difference, to implement the above operations. We can consider each booking as booking seats
seats on all flights within a certain interval [first, last]
. Therefore, for each booking, we add seats
to the first
position of the binary indexed tree and subtract seats
from the last + 1
position of the binary indexed tree. Finally, we calculate the prefix sum for each position in the binary indexed tree to get the total number of seats booked for each flight.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the number of flights.
Here is a basic introduction to the binary indexed tree:
A binary indexed tree, also known as a “Binary Indexed Tree” or Fenwick tree. It can efficiently implement the following two operations:
 Single Point Update
update(x, delta)
: Add a value delta to the number at position x in the sequence;  Prefix Sum Query
query(x)
: Query the interval sum of the sequence[1,...x]
, that is, the prefix sum of position x.
The time complexity of these two operations is $O(\log n)$.

class Solution { public int[] corpFlightBookings(int[][] bookings, int n) { int[] ans = new int[n]; for (var e : bookings) { int first = e[0], last = e[1], seats = e[2]; ans[first  1] += seats; if (last < n) { ans[last] = seats; } } for (int i = 1; i < n; ++i) { ans[i] += ans[i  1]; } return ans; } }

class Solution { public: vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) { vector<int> ans(n); for (auto& e : bookings) { int first = e[0], last = e[1], seats = e[2]; ans[first  1] += seats; if (last < n) { ans[last] = seats; } } for (int i = 1; i < n; ++i) { ans[i] += ans[i  1]; } return ans; } };

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))

func corpFlightBookings(bookings [][]int, n int) []int { ans := make([]int, n) for _, e := range bookings { first, last, seats := e[0], e[1], e[2] ans[first1] += seats if last < n { ans[last] = seats } } for i := 1; i < n; i++ { ans[i] += ans[i1] } return ans }

/** * @param {number[][]} bookings * @param {number} n * @return {number[]} */ var corpFlightBookings = function (bookings, n) { const ans = new Array(n).fill(0); for (const [first, last, seats] of bookings) { ans[first  1] += seats; if (last < n) { ans[last] = seats; } } for (let i = 1; i < n; ++i) { ans[i] += ans[i  1]; } return ans; };

impl Solution { #[allow(dead_code)] pub fn corp_flight_bookings(bookings: Vec<Vec<i32>>, n: i32) > Vec<i32> { let mut ans = vec![0; n as usize]; // Build the difference vector first for b in &bookings { let (l, r) = ((b[0] as usize)  1, (b[1] as usize)  1); ans[l] += b[2]; if r < (n as usize)  1 { ans[r + 1] = b[2]; } } // Build the prefix sum vector based on the difference vector for i in 1..n as usize { ans[i] += ans[i  1]; } ans } }