×

Search anything:

# Corporate Flight Bookings problem [Solved]

#### prefix sum array Algorithms

Get this book -> Problems on Array: For Interviews and Competitive Programming

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.

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

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.

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.

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.

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.
}
}
};
``````

Time and Space complexity

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

## Approach 2: Prefix sum approach

Algorithm

• 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

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

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

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

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.
[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]

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

}
};
``````

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.

#### Abrham Lakew

Electrical and Computer Engineer, Completed Engineer's degree in Electrical and Computer Engineering at Addis Abeba Science and Technology. SDE Intern at OpenGenus.

Improved & Reviewed by:

Corporate Flight Bookings problem [Solved]