Last Updated: 19 Apr, 2021

Corporate Flight Bookings

Easy

Asked in company

Solve now

Problem statement

You have been given an array/list “BOOKINGS” of booking details of ‘N’ flights from 1 to ‘N’. Each booking detail contains three positive integers [first, last, seats] which represent a booking for flights “first” through “last” (inclusive) with “seats” seats reserved for each flight in the range.

Now, you are supposed to return an array/list “ANSWER” of length ‘N’, where answer[i] represents the total number of seats reserved for ith flight.

Input Format :

The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first input line of each test case contains two space-separated integers ‘N’ and ‘M’ denoting the number of flights and booking details, respectively.

Each of the next ‘M’ lines contains three space-separated integers [first, last, seats] denoting the booking details.

Output Format :

For each test case, print the ‘N’ space-separated integers denoting the elements of the “ANSWER” array/list.

Print the output of each test case in a separate line.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 50
1 <= N, M <= 10^4
1 <= first, last <= N
1 <= seats <= 10^3

Where ‘T’ is the number of test cases, ‘N’ is the number of flights, ‘M’ is the length of booking details array/list and the three integers [first, last, seats] denote the details of a booking.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach: The basic idea for this approach is to traverse through each booking detail and then iterate through the range of flights for updating the count of reserved seats for each flight.

Consider the following steps:

Create an empty array/list 'ANSWER' to store the total number of seats reserved for ith flight (0-based indexing).
Now, traverse through each booking detail.
- Let [START, END, SEATS] be the current booking detail.
- Now, iterate through the flights from 'START' to 'END' and increment the count of reserved 'SEATS' for each flight.
- Create a loop using a variable ‘i’ such that 'START' <= 'i' <= ‘END’
  - ANSWER[i - 1] = ANSWER[i - 1] + 'SEATS'
Return the “answer”.

Solve now

02 Approach

Approach: The idea here is not to iterate through ‘START’ to ‘END’ for a booking detail. Instead, we can simply update the ‘ANSWER’ array/list as

ANSWER[START - 1] = ANSWER[START - 1] + SEATS
Now, if 'END' is not equal to ‘N’, ANSWER[END] = ANSWER[END] - SEATS

Now, we can simply take the prefix sum over the 'ANSWER' array/list to get the answer.

Let us take test case 1 of sample testcase 1 as an example where booking = [ [1, 2, 3], [2, 3, 2], [1, 3, 1], [3, 4, 2] ]

Traverse the booking array/list and update the “answer” which is initially [0, 0, 0, 0]

For booking, [1, 2, 3], start = 1, end = 2, seats = 3.
1. answer[0] = answer[0] + 3 => answer = [3, 0, 0, 0]
2. answer[2] = answer[2] - 3. => answer = [3, 0, -3, 0]
For booking, [2, 3, 2], start = 2, end = 3, seats = 2.
1. answer[1] = answer[1] + 2 => answer = [3, 2, 0, 0]
2. answer[3] = answer[3] - 2. => answer = [3, 2, -3, -2]
For booking, [1, 3, 1], start = 1, end = 3, seats = 1.
1. answer[0] = answer[0] + 1 => answer = [4, 2, -3, -2]
2. answer[3] = answer[3] - 1. => answer = [4, 2, -3, -3]
For booking, [3, 4, 2], start = 3, end = 4, seats = 2.
1. answer[2] = answer[2] + 2 => answer = [4, 2, -1, -3]

Now, we will take the prefix sum.

answer[1] = answer[1] + answer[0] => answer = [4, 6, -1, -3]
answer[2] = answer[2] + answer[1] => answer = [4, 6, 5, -3]
answer[3] = answer[3] + answer[2] => answer = [4, 6, 5, 2]

Algorithm:

Create an empty array/list ‘ANSWER’ to store the total number of seats reserved for ith flight (0-based indexing).
Now, traverse through each booking detail.
- Let [START, END, SEATS] be the current booking detail.
- Update “ANSWER[START - 1]” as ANSWER[START - 1] = ANSWER[START - 1] + SEATS.
- If end is not equal to ‘N’ then, update ‘ANSWER[END]’ as ANSWER[END] = ANSWER[END] - SEATS.
Now, create a loop using a variable ‘i’ such that 1 <= ‘i’ < ‘N’ for prefix sum
- Update 'ANSWER[i]' as ANSWER[i] = ANSWER[i] + ANSWER[i - 1]
Return the ‘ANSWER’.

Solve now