1109. Corporate Flight Bookings


Problem Description

In this problem, we are managing a system that tracks flight bookings. We are given n flights, which are identified by numbers ranging from 1 to n. Additionally, we are provided with an array named bookings. Each entry in this array is another array that contains three elements, [first_i, last_i, seats_i]. This entry indicates a booking for multiple flights - from flight number first_i to flight number last_i (inclusive) - and each flight in this range has seats_i seats reserved.

The task is to compute and return an array, answer, which has the same length as the number of flights (n). Each element in answer should represent the total number of seats booked for the corresponding flight. In other words, answer[i] should tell us how many seats have been reserved for the ith flight.

Intuition

The key to solving this problem is recognizing that the range update operation (booking seats for a range of flights) can be efficiently tracked using the concept of difference arrays. A difference array can allow us to apply the effects of a range update in constant time and later reconstruct the original array with the complete effects applied.

The intuition behind using a difference array is as follows:

  • When seats are booked from flight first_i to last_i, we do not necessarily need to add seats_i to each entry between first_i and last_i in the answer array. Instead, we could record the seats_i addition at the start index first_i - 1 (since arrays are zero-indexed) and a negation of seats_i at the index last_i, indicating the end of the booking range.
  • What this achieves is a sort of "bookend" model, where we place a marker for where seats start being added and where they stop. This is somewhat akin to noting down the start and end of a chalk mark without having to color in the whole segment.

Once we have made these updates to our answer array, which now serves as a difference array, we need to accumulate the effects to find out the total number of seats booked for each flight. Accumulating from left to right will add seats_i from the start index up until the end index, effectively applying the range update.

  • For example, if we add 10 seats at index 0 (flight 1) and subtract 10 seats at index 5 (after flight 5), accumulating the values will result in each of the first 5 elements showing an increment of 10, and the increment will no longer apply from position 6 onward.
  • The key operation to accomplish the accumulation efficiently in our Python code is to utilize the accumulate function from the itertools module.

This approach takes us from a brute-force method that might involve multiple iterations per booking (which would be inefficient and potentially time-consuming for a large number of bookings or flights) to a much more efficient algorithm with a time complexity that is linear with respect to the number of flights and bookings.

Learn more about Prefix Sum patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

Let's break down the implementation provided in the reference solution and see how it applies the intuition that we discussed above.

  1. Initialize an array ans of zeros with the same length as the number of flights (n). This array will serve as our difference array where we'll apply the updates from the bookings and later accumulate these updates to get the final answer.

    1ans = [0] * n
  2. Iterate over each booking in the bookings array. For each booking:

    • Increase the element at the index (first - 1) in the ans by seats. This corresponds to the start of the booking range where the seats begin to be reserved.
    • If the last flight in the booking is not the very last flight available, then decrease the element at the index last in the ans by seats. This will indicate the end of the booking range where the reserved seats are no longer available.
    1for first, last, seats in bookings:
    2    ans[first - 1] += seats
    3    if last < n:
    4        ans[last] -= seats
  3. Use the accumulate function to accumulate the elements of ans. This Python function takes a list and returns a list where each element is the cumulative total from the first element to the current one. This effectively reconstructs the resulting array where each element represents the total number of seats reserved for the corresponding flight after applying all bookings. Since the ans array at this stage is a difference array, the accumulation will give us the true number of seats reserved for each flight.

    1return list(accumulate(ans))

In terms of data structures, the problem makes essential use of an array data structure. The algorithmic pattern used here is the "difference array" pattern, which enables us to efficiently apply range updates (in O(1) time) and then reconstruct the original array with a single pass to accumulate these changes (in O(n) time).

The overall algorithm can be summarized in the following steps:

  • Initialize a difference array with zeros
  • Apply the range update operations to the difference array
  • Accumulate the difference array to reconstruct the final answer

This approach is much more efficient than directly applying increments to a range of elements within the array for each booking, especially when dealing with a large number of flights and bookings.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which two pointer technique does Quick Sort use?

Example Walkthrough

Let's use a small example to illustrate the solution approach.

Suppose we have n = 5 flights, and we receive the following bookings: [[1, 2, 10], [2, 3, 20], [3, 5, 25]]. This means:

  • 10 seats are booked for flights 1 and 2.
  • 20 seats are booked for flights 2 and 3.
  • 25 seats are booked for flights 3 to 5 (inclusive).

We start with an array ans initialized with zeros, with the same length as the number of flights (n), thus ans = [0, 0, 0, 0, 0].

Now, we iterate over each booking and update the ans array:

  1. For the first booking [1, 2, 10], we add 10 seats at index 0 and subtract 10 seats at index 2.

    • Before: ans = [0, 0, 0, 0, 0]
    • After: ans = [10, 0, -10, 0, 0]
  2. For the second booking [2, 3, 20], we add 20 seats at index 1 and subtract 20 seats at index 3.

    • Before: ans = [10, 0, -10, 0, 0]
    • After: ans = [10, 20, -10, -20, 0]
  3. For the third booking [3, 5, 25], we add 25 seats at index 2 and there is no need to subtract at the end since the booking range includes the last flight.

    • Before: ans = [10, 20, -10, -20, 0]
    • After: ans = [10, 20, 15, -20, 0]

Finally, we use the accumulate function to build the answer from the ans difference array:

  • Accumulate: [10, 30, 45, 25, 25]
  • This means the total number of seats booked for each flight is 10, 30, 45, 25, and 25, respectively.

The final result of our algorithm gives us the array [10, 30, 45, 25, 25], which indicates the total number of seats reserved for each flight from 1 to 5 after all the bookings have been applied.

This example demonstrates the effectiveness of the difference array pattern in managing range updates efficiently. By applying incremental updates at the start and a decremental update at the end of each booking range, we avoid multiple iterations over the range for each booking. Once all the incremental and decremental updates are applied, accumulating the changes provides the total number of booked seats for each flight.

Not Sure What to Study? Take the 2-min Quiz:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Python Solution

1from typing import List
2from itertools import accumulate
3
4class Solution:
5    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
6        # Initialize a result list to hold the number of seats booked for each flight
7        flight_seats = [0] * n
8      
9        # Iterate through each booking to update flight_seats
10        for start, end, seats in bookings:
11            # Increase the seats count at the start index
12            flight_seats[start - 1] += seats
13          
14            # Decrease the seats count at the index after the end to nullify the increase
15            # which will happen due to prefix sum (accumulate) later
16            if end < n:
17                flight_seats[end] -= seats
18      
19        # Calculate the prefix sum which gives the total number of seats booked
20        # for each flight from the beginning
21        return list(accumulate(flight_seats))
22

Java Solution

1class Solution {
2  
3    /* 
4    This method calculates the number of seats booked on each flight.
5  
6    Parameters:
7    bookings - an array of bookings, where bookings[i] = [first_i, last_i, seats_i]
8    n - the number of flights
9  
10    Returns:
11    an array containing the total number of seats booked for each flight.
12    */
13    public int[] corpFlightBookings(int[][] bookings, int n) {
14        // Initialize an array to hold the answer, with n representing the number of flights.
15        int[] answer = new int[n];
16      
17        // Iterate over each booking.
18        for (int[] booking : bookings) {
19            // Extract the start and end flight numbers and the number of seats booked.
20            int startFlight = booking[0];
21            int endFlight = booking[1];
22            int seats = booking[2];
23          
24            // Increment the seats for the start flight by the number of seats booked.
25            answer[startFlight - 1] += seats;
26          
27            // If the end flight is less than the number of flights,
28            // decrement the seats for the flight immediately after the end flight.
29            if (endFlight < n) {
30                answer[endFlight] -= seats;
31            }
32        }
33      
34        // Iterate over the answer array, starting from the second element,
35        // and update each position with the cumulative sum of seats booked so far.
36        for (int i = 1; i < n; ++i) {
37            answer[i] += answer[i - 1];
38        }
39      
40        // Return the populated answer array.
41        return answer;
42    }
43}
44

C++ Solution

1class Solution {
2public:
3    // Function to calculate how many seats are booked on each flight
4    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
5        vector<int> seatsBooked(n); // Array to store the final number of seats booked for each flight
6      
7        // Loop over all the booking records
8        for (auto& booking : bookings) {
9            int startFlight = booking[0]; // Start flight number of the booking
10            int endFlight = booking[1];   // End flight number of the booking
11            int seats = booking[2];       // Number of seats to be booked in this range
12          
13            // Increment the seats booked for the start flight by the number of seats booked
14            seatsBooked[startFlight - 1] += seats;
15          
16            // If the booking ends before the last flight, decrement the seats booked
17            // for the first flight after the end flight. This will be used later for
18            // calculating cumulative sum.
19            if (endFlight < n) {
20                seatsBooked[endFlight] -= seats;
21            }
22        }
23      
24        // Calculate the cumulative sum to get the actual number of seats booked for each flight
25        for (int i = 1; i < n; ++i) {
26            seatsBooked[i] += seatsBooked[i - 1];
27        }
28      
29        // Return the final results
30        return seatsBooked;
31    }
32};
33

Typescript Solution

1/**
2 * This function takes a list of bookings and the total number of flights (n),
3 * and returns an array where each element represents the total number of seats
4 * booked on that flight.
5 *
6 * @param {number[][]} bookings - A list where each element is a booking in the
7 * form [first, last, seats] indicating a booking from flight `first` to flight
8 * `last` (inclusive) with `seats` being the number of seats booked.
9 * @param {number} n - The total number of flights.
10 * @return {number[]} - An array representing the total number of seats booked
11 * on each flight.
12 */
13const corpFlightBookings = (bookings: number[][], n: number): number[] => {
14    // Initialize answer array with n elements set to 0.
15    const answer: number[] = new Array(n).fill(0);
16
17    // Loop through each booking.
18    for (const [first, last, seats] of bookings) {
19        // Increment the seats for the first flight in the current booking range.
20        answer[first - 1] += seats;
21        // Decrement the seats for the flight just after the last flight in
22        // the current booking range, if it is within bounds.
23        if (last < n) {
24            answer[last] -= seats;
25        }
26    }
27
28    // Aggregate the booked seats information.
29    // Each flight's bookings include its own and also the cumulative bookings
30    // from the previous flight. This is because the seats booked in the flight ranges
31    // overlap and the initial range difference accounted for it.
32    for (let i = 1; i < n; ++i) {
33        answer[i] += answer[i - 1];
34    }
35
36    // Return the final aggregated information about flight bookings.
37    return answer;
38};
39
Fast Track Your Learning with Our Quick Skills Quiz:

A heap is a ...?

Time and Space Complexity

The time complexity of the provided code is composed of two parts: the iteration through the bookings list and the accumulation of the values in the ans array.

The iteration through the bookings list happens once for each booking. For each booking, the code performs constant-time operations: an increment at the start position and a decrement at the end position. Therefore, if there are k bookings, this part has a time complexity of O(k).

The accumulate function is used to compute the prefix sums of the ans array, which has n elements. This operation is linear in the number of flights, so it has a time complexity of O(n).

Combining these two parts, the overall time complexity of the code is O(k + n), since we have to consider both the number of bookings and the number of flights.

The space complexity of the code is primarily determined by the storage used for the ans array, which has n elements. The accumulate function returns an iterator in Python, so it does not add additional space complexity beyond what is used for the ans array. Therefore, the space complexity of the provided code is O(n).

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫