Corporate Flight Bookings
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

Question

Corporate Flight Bookings

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

Accepted Answer

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:

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

Space Complexity: O(n)Explanation:

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).

Time Complexity: OtherExplanation:

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).

Java (SE 1.8)

/*
    Time Complexity: O(N * M)
    Space Complexity: O(N)

    where 'N' is the number of flights and 'M' is the length of booking details array/list.
*/

import java.util.ArrayList;

public class Solution {
    public static ArrayList < Integer > corpFlightBookings(ArrayList < ArrayList < Integer >> bookings, int n) {
        
        // To store the total number of seats reserved for i-th flight (0-based indexing).
        ArrayList < Integer > answer = new ArrayList < Integer > ();
        for(int i = 0; i < n; i++){
            answer.add(0);
        }

        for (int j = 0; j < bookings.size(); j++) {
            for (int i = bookings.get(j).get(0); i <= bookings.get(j).get(1); i++) {
                // Increment the count of reserved seats.
                answer.set(i - 1, answer.get(i - 1) + bookings.get(j).get(2));
            }
        }

        return answer;
    }
}

Python (3.5)

'''

    Time Complexity: O(N * M)

    Space Complexity: O(N)



    where 'N' is the number of flights and 'M' is the length of booking details array/list.

'''



def corpFlightBookings(bookings, n):

	# To store the total number of seats reserved for i-th flight (0-based indexing).

	answer = [0 for i in range(n)]



	for booking in bookings:

		for i in range(booking[0], booking[1] + 1):

			# Increment the count of reserved seats.

			answer[i - 1] = answer[i - 1] + booking[2]

		

	return answer

C++ (g++ 5.4)

/*
    Time Complexity: O(N * M)
    Space Complexity: O(N)

    where 'N' is the number of flights and 'M' is the length of booking details array/list.
*/

vector < int > corpFlightBookings(vector < vector < int >> & bookings, int n) {
    // To store the total number of seats reserved for i-th flight (0-based indexing).
    vector < int > answer(n, 0);

    for (vector < int > booking: bookings) {
        for (int i = booking[0]; i <= booking[1]; i++) {
            // Increment the count of reserved seats.
            answer[i - 1] = answer[i - 1] + booking[2];
        }
    }

    return answer;
}

Accepted Answer

Optimised 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’.