Corporate Flight Bookings problem [Solved]

In this article, we will solve Corporate Flight Bookings problem using prefix sum algorithm. In naive approach, it will take a quadratic O(N^2) time complexity but using a prefix sum approach we can get better time complexity.

Table of contents:

1. Problem Statement
2. Approach 1: Naive method
3. Approach 2: Prefix sum approach

Problem Statement

The Corporate Flight Bookings problem is a problem of finding the total seats reserved for each n flights. we are given i length bookings array which contains a subarray of each first up to last seats of the booking i. The prefix sum approach will do better to solve this problem.

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
Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5

we have 5 flight labels.

Booking 1 reserved:  10  10(starting from the 1st flight to the 2nd flight)
Booking 2 reserved:      20  20(starting from the 2nd flight to the third flight)
Booking 3 reserved:      25  25  25  25(starting from the 2nd flight to n)
Total seats:         10  55  45  25  25

Let us implement using two approaches.

Approach 1: Naive method

Algorithm

• Store the seats value of each flight at an array called answer.
• Iterate through all the values of the bookings.
• for each bookings subarray increment answer by the seats value startig from the first flight to the last flight.

Explanation:

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Note: bookings[i] = [firsti, lasti, seatsi]

Let us create answer array of length n

answer = [0,0,0,0,0]
For the first booking, which is [1,2,10] we increment the answer array by 10(seats value) from the the index 0 to 1. our array is zero indexed so we subtract 1 from both the first and last.
answer = [10,10,0,0,0]

For the second, which is [2,3,20] we increment the answer array by 20(seats value) from the index 1 to 2. our array is zero indexed so we subtract 1 from both the first and last.
answer = [10,30,20,0,0]

For the third, which is [2,5,25] we increment the answer array by 20(seats value) from the the index 1 to 4. our array is zero indexed so we subtract 1 from both the first and last.
answer = [10,30,45,25,25]

Javascript implementation

var corpFlightBookings = function(bookings, n) {
       let answer = new Array(n).fill(0); // create an array of answer with length of n and with data type of integer(i.e fill all the elements with 0)
        for (let i=0; i<bookings.length; i++) {   // iterate through the bookings array. 
            for (let j=bookings[i][0]-1; j<bookings[i][1]; j++) { // iterate through each bookings subarray.
               answer[j]+=bookings[i][2]; // update each of the answer elements with seats value
            }
        }
        return answer;
};

Time and Space complexity

The time complexity: O(N^2)
The space complexity: O(N)

Approach 2: Prefix sum approach

Algorithm

• create answer array
• Increment answer at index = booking[i] first - 1 by bookings[i] seats
• Decrement answer at index = booking[i] last by bookings[i] seats
• perform prefix sum array on answer

Explanation

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Note: bookings[i] = [firsti, lasti, seatsi]

create an array
answer = [0,0,0,0,0]

when i = 0
Increment answer at index = booking[0] first - 1 by bookings[0] seats
index = 1 - 1 = 0;
answer = [10,0,0,0,0]
Decrement answer at index = booking[0] last by bookings[0] seats
index = 2
answer = [10,0,-10,0,0]

when i = 1
Increment answer at index = booking[1] first - 1 by bookings[1] seats
index = 2 - 1 = 1;
answer = [10,20,0,0,0]
Decrement answer at index = booking[1] last by bookings[1] seats
index = 3
answer = [10,20,-10,-20,0]

when i = 2
Increment answer at index = booking[2] first - 1 by bookings[2] seats
index = 2 - 1 = 1;
answer = [10,45,-10,-20,0]
Decrement answer at index = booking[2] last by bookings[2] seats
index = 5 = n leave as it is
answer = [10,45,-10,-20,0]

Performing prefix sum:
prefix sum array is the element at index i is the sum of the current element(i) and the previous element(i-1) which is the sum of all elements before it.
answer = [10,45,-10,-20,0] -> [10,55,-10,-20,0]
[10,55,-10,-20,0] -> [10,55,45,-20,0]
[10,55,45,-20,0] -> [10,55,45,25,0]
[10,55,45,25,0] -> [10,55,45,25,25]

answer = [10,55,45,25,25]

Javascript implementation

     var corpFlightBookings = function(bookings, n) {
        let answer = new Array(n).fill(0);    // create an array of answer with length of n and with data type of integer(i.e fill all the elements with 0)
        for (let i=0; i<bookings.length; i++) {     // iterate through the bookings array
            answer[bookings[i][0]-1] += bookings[i][2];  // increment answer element at index *firsti - 1* with its seats value.
            if (bookings[i][1] < n) {
               answer[bookings[i][1]] -=  bookings[i][2]; // decrement answer element at index *lasti* only if *lasti* is less than *n*
            }
        }
        
        //prfix sum
        for (let i=1; i<n; i++) {
            answer[i]+=answer[i-1]; // update *answer i* with the sum of the *answer i* and previous answer(*answeri - 1*)
            
        }
        return answer;
      };

Time and Space Complexity

Time Complexity O(N+M), O(N) is for the first loop and O(M) is the second loop which is used to implement the prefix sum.
Space complexity O(N)

With this article at OpenGenus, you must have the complete idea of solving this problem of Corporate Flight Bookings.