Corporate Flight Bookings

Posted: 19 Apr, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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
Approach 1

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:

  1. Create an empty array/list 'ANSWER' to store the total number of seats reserved for ith flight (0-based indexing).
  2. 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'
  3. Return the “answer”.
Try Problem