Corporate Flight Bookings

Easy
0/40
Average time to solve is 15m
profile
Contributed by
24 upvotes
Asked in company
Wells Fargo

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
4 4
1 2 3
2 3 2
1 3 1
3 4 2 
1 1
1 1 7

Sample output 1 :

4 6 5 2
7

Explanation For Sample Input 1 :

For the first test case,
Flight labels:               1   2   3   4
Booking 1 reserved:          3   3
Booking 2 reserved:              2   2
Booking 3 reserved:          1   1   1
Booking 4 reserved:                  2   2    
Total seats:                 4   6   5   2
Hence, answer = [4, 6, 5, 2].

For the second test case, there is only one flight and single booking detail. So, answer = [7].

Sample Input 2 :

2
3 2
1 2 2
2 3 3
2 1
1 2 1

Sample output 2 :

2 5 3
1 1

Explanation For Sample Input 2 :

For the first test case,
Flight labels:              1   2   3
Booking 1 reserved:         2   2
Booking 2 reserved:             3   3
Total seats:                2   5   3
Hence, answer = [2, 5, 3].

For the second test case, answer = [1, 1].
Hint

Can you think of a brute force solution?

Approaches (2)
Brute Force

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”.
Time Complexity

O(N * M), where 'N’ is the number of flights and ‘M’ is the length of booking details array/list 

 

Since we are traversing through the booking details array/list of length ‘M’ and at each iteration, we are updating the “ANSWER” array/list which will take O(N). So, the overall time complexity will be O(N * M).

Space Complexity

O(N), where ‘N’ is the number of flights.

 

Since we are storing the count of reserved seats in an array/list of length ‘N’, so the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Corporate Flight Bookings
Full screen
Console