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] = [firsti, lasti, seatsi] represents a booking for flights firsti through lasti (inclusive) with seatsi 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 * 104
  • 1 <= bookings.length <= 2 * 104
  • bookings[i].length == 3
  • 1 <= firsti <= lasti <= n
  • 1 <= seatsi <= 104

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:

  1. Single Point Update update(x, delta): Add a value delta to the number at position x in the sequence;
  2. 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[first-1] += seats
		if last < n {
			ans[last] -= seats
		}
	}
	for i := 1; i < n; i++ {
		ans[i] += ans[i-1]
	}
	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
    }
}

All Problems

All Solutions