Count of seats booked on each of the given N flights

0 0 9 minutes read

Given an integer N denoting the number of flights and array bookings[][3] with each row of the form {a, b, K} denoting that there are K seats booked from flight a to flight b ( consider 1-based indexing), the task is to find the sequence of the number of seats booked in N flights.

Examples:

Input: bookings[][] = {{1, 2, 10}, {2, 3, 20}, {2, 5, 25}}
Output: 10 55 45 25 25
Explanation:
Initially, there are no seats booked in any of the flights. So the resultant sequence is {0, 0, 0, 0, 0}
Book 10 seats in flights 1 to 2. The sequence becomes {10, 10, 0, 0, 0}.
Book 20 seats in flights 2 to 3. The sequence becomes {10, 30, 20, 0, 0}.
Book 25 seats in flights 2 to 5. The sequence becomes {10, 55, 45, 25, 25}.

Input: bookings[][] = {{1, 3, 100}, {2, 6, 100}, {3, 4, 100}}
Output: 100 200 300 200 100 100

Naive Approach: Follow the steps below to solve the problem in simplest approach possible:

Initialize an array seq[] of size N to store the count of allocated seats in each flight.
Traverse the array bookings[].
For each query {a, b, K}, add the element K in the array seq[] from the index a to b.
After completing the above steps, print the array seq[] as the result.

Below is the code for the above naive approach :

C++

// C++ program for the naive approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the total of the
// seats booked in each of the flights
void corpFlightBookings(vector<vector<int> >& Bookings,
                        int N)
{
    // Initialize the array to store the count of
    // allocated seats in each flight to zero
    vector<int> seq(N, 0);
    // Traverse the array
    for (int i = 0; i < Bookings.size(); i++) {
 
        // Store the first booked flight
        int l = Bookings[i][0];
 
        // Store the last booked flight
        int r = Bookings[i][1];
 
        // Store the total number of
        // seats booked in flights [l, r]
        int K = Bookings[i][2];
 
        // Add K to each flight from L to R
        for (int j = l - 1; j < r; j++) {
            seq[j] += K;
        }
    }
 
    // Print the total number of seats
    // booked in each flight
    for (int i = 0; i < seq.size(); i++) {
        cout << seq[i] << " ";
    }
}
 
// Driver Code
int main()
{
    // Given list of bookings
    vector<vector<int> > bookings{ { 1, 3, 100 },
                                   { 2, 6, 100 },
                                   { 3, 4, 100 } };
    int N = 6;
    // Function Call
    corpFlightBookings(bookings, N);
 
    return 0;
}

Java

import java.util.ArrayList;
import java.util.List;
 
public class CorporateFlightBookings {
 
    // Function to find the total seats booked in each flight
    static void corpFlightBookings(List<List<Integer>> bookings, int N) {
        // Initialize an array to store the count of allocated seats in each flight to zero
        int[] seq = new int[N];
 
        // Traverse the list of bookings
        for (List<Integer> booking : bookings) {
            // Extract booking information
            int l = booking.get(0); // First booked flight
            int r = booking.get(1); // Last booked flight
            int K = booking.get(2); // Total number of seats booked
 
            // Add K to each flight from L to R
            for (int j = l - 1; j < r; j++) {
                seq[j] += K;
            }
        }
 
        // Print the total number of seats booked in each flight
        for (int i = 0; i < seq.length; i++) {
            System.out.print(seq[i] + " ");
        }
    }
 
    public static void main(String[] args) {
        // Given list of bookings
        List<List<Integer>> bookings = new ArrayList<>();
        bookings.add(List.of(1, 3, 100));
        bookings.add(List.of(2, 6, 100));
        bookings.add(List.of(3, 4, 100));
        int N = 6;
 
        // Function Call
        corpFlightBookings(bookings, N);
    }
}

Python3

# Function to calculate the total of the
# seats booked in each of the flights
def corpFlightBookings(bookings, N):
    # Initialize the array to store the count of
    # allocated seats in each flight to zero
    seq = [0] * N
 
    # Traverse the list of bookings
    for i in range(len(bookings)):
        # Store the first booked flight
        l = bookings[i][0]
 
        # Store the last booked flight
        r = bookings[i][1]
 
        # Store the total number of seats booked in flights [l, r]
        K = bookings[i][2]
 
        # Add K to each flight from L to R
        for j in range(l - 1, r):
            seq[j] += K
 
    # Print the total number of seats booked in each flight
    for i in range(len(seq)):
        print(seq[i], end=" ")
 
# Driver Code
if __name__ == "__main__":
    #list of bookings
    bookings = [[1, 3, 100],
                [2, 6, 100],
                [3, 4, 100]]
    N = 6
    corpFlightBookings(bookings, N)

C#

using System;
using System.Collections.Generic;
 
class Program
{
    // Function to find the total of the seats booked in each of the flights
    static void CorpFlightBookings(List<List<int>> bookings, int N)
    {
        // Initialize the array to store the count of allocated seats in each flight to zero
        int[] seq = new int[N];
 
        // Traverse the list of bookings
        foreach (var booking in bookings)
        {
            // Store the first booked flight
            int l = booking[0];
 
            // Store the last booked flight
            int r = booking[1];
 
            // Store the total number of seats booked in flights [l, r]
            int K = booking[2];
 
            // Add K to each flight from L to R
            for (int j = l - 1; j < r; j++)
            {
                seq[j] += K;
            }
        }
 
        // Print the total number of seats booked in each flight
        for (int i = 0; i < seq.Length; i++)
        {
            Console.Write(seq[i] + " ");
        }
    }
 
    static void Main()
    {
        // Given list of bookings
        List<List<int>> bookings = new List<List<int>>
        {
            new List<int> {1, 3, 100},
            new List<int> {2, 6, 100},
            new List<int> {3, 4, 100}
        };
        int N = 6;
 
        // Function Call
        CorpFlightBookings(bookings, N);
    }
}

Output

100 200 300 200 100 100

Time Complexity: O(N²)
Auxiliary Space: O(N)

Efficient Approach: To optimize the above approach, the idea is to use the concept of Prefix Sum. Follow the steps below to solve the problem:

Initialize an array seq[] of size (N + 2) to store all the allocated seats.
Traverse the array bookings[].
For each query {a, b, K}, increment the array seq[] at index (a – 1) by K and decrement the element at index (b + 1) by K.
For the resulting sequence, find the prefix sum of the array seq[].
After completing the above steps, print the array seq[] as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the total of the
// seats booked in each of the flights
void corpFlightBookings(
    vector<vector<int> >& Bookings,
    int N)
{
    // Stores the resultant sequence
    vector<int> res(N, 0);
 
    // Traverse the array
    for (int i = 0;
         i < Bookings.size(); i++) {
 
        // Store the first booked flight
        int l = Bookings[i][0];
 
        // Store the last booked flight
        int r = Bookings[i][1];
 
        // Store the total number of
        // seats booked in flights [l, r]
        int K = Bookings[i][2];
 
        // Add K to the flight L
        res[l - 1] = res[l - 1] + K;
 
        // Subtract K from flight
        // number R + 1
        if (r <= res.size() - 1)
            res[r] = (-K) + res[r];
    }
 
    // Find the prefix sum of the array
    for (int i = 1; i < res.size(); i++)
        res[i] = res[i] + res[i - 1];
 
    // Print the total number of seats
    // booked in each flight
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << " ";
    }
}
 
// Driver Code
int main()
{
    // Given list of bookings
    vector<vector<int> > bookings{ { 1, 3, 100 },
                                   { 2, 6, 100 },
                                   { 3, 4, 100 } };
    int N = 6;
 
    // Function Call
    corpFlightBookings(bookings, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG
{
 
// Function to find the total of the
// seats booked in each of the flights
static void corpFlightBookings(int [][]Bookings,
                               int N)
{
   
    // Stores the resultant sequence
    int res[] = new int[N];
 
    // Traverse the array
    for (int i = 0;
         i < Bookings.length; i++)
    {
 
        // Store the first booked flight
        int l = Bookings[i][0];
 
        // Store the last booked flight
        int r = Bookings[i][1];
 
        // Store the total number of
        // seats booked in flights [l, r]
        int K = Bookings[i][2];
 
        // Add K to the flight L
        res[l - 1] = res[l - 1] + K;
 
        // Subtract K from flight
        // number R + 1
        if (r <= res.length - 1)
            res[r] = (-K) + res[r];
    }
 
    // Find the prefix sum of the array
    for (int i = 1; i < res.length; i++)
        res[i] = res[i] + res[i - 1];
 
    // Print the total number of seats
    // booked in each flight
    for (int i = 0; i < res.length; i++)
    {
        System.out.print(res[i] + " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
   
    // Given list of bookings
    int bookings[][] = { { 1, 3, 100 },
                        { 2, 6, 100 },
                        { 3, 4, 100 } };
    int N = 6;
 
    // Function Call
    corpFlightBookings(bookings, N);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program for the above approach
 
# Function to find the total of the
# seats booked in each of the flights
def corpFlightBookings(Bookings, N):
   
    # Stores the resultant sequence
    res = [0] * N
 
    # Traverse the array
    for i in range(len(Bookings)):
 
        # Store the first booked flight
        l = Bookings[i][0]
 
        # Store the last booked flight
        r = Bookings[i][1]
 
        # Store the total number of
        # seats booked in flights [l, r]
        K = Bookings[i][2]
 
        # Add K to the flight L
        res[l - 1] = res[l - 1] + K
 
        # Subtract K from flight
        # number R + 1
        if (r <= len(res) - 1):
            res[r] = (-K) + res[r]
 
    # Find the prefix sum of the array
    for i in range(1, len(res)):
        res[i] = res[i] + res[i - 1]
 
    # Print total number of seats
    # booked in each flight
    for i in range(len(res)):
        print(res[i], end = " ")
 
# Driver Code
if __name__ == '__main__':
   
    # Given list of bookings
    bookings = [ [ 1, 3, 100 ],
               [ 2, 6, 100 ],
               [ 3, 4, 100 ] ]
    N = 6
 
    # Function Call
    corpFlightBookings(bookings, N)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
class GFG
{
 
// Function to find the total of the
// seats booked in each of the flights
static void corpFlightBookings(int [,]Bookings,
                               int N)
{
   
    // Stores the resultant sequence
    int []res = new int[N];
 
    // Traverse the array
    for (int i = 0;
         i < Bookings.GetLength(0); i++)
    {
 
        // Store the first booked flight
        int l = Bookings[i,0];
 
        // Store the last booked flight
        int r = Bookings[i,1];
 
        // Store the total number of
        // seats booked in flights [l, r]
        int K = Bookings[i,2];
 
        // Add K to the flight L
        res[l - 1] = res[l - 1] + K;
 
        // Subtract K from flight
        // number R + 1
        if (r <= res.Length - 1)
            res[r] = (-K) + res[r];
    }
 
    // Find the prefix sum of the array
    for (int i = 1; i < res.Length; i++)
        res[i] = res[i] + res[i - 1];
 
    // Print the total number of seats
    // booked in each flight
    for (int i = 0; i < res.Length; i++)
    {
        Console.Write(res[i] + " ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
   
    // Given list of bookings
    int [,]bookings = { { 1, 3, 100 },
                        { 2, 6, 100 },
                        { 3, 4, 100 } };
    int N = 6;
 
    // Function Call
    corpFlightBookings(bookings, N);
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to find the total of the
// seats booked in each of the flights
function corpFlightBookings(Bookings, N)
{
     
    // Stores the resultant sequence
    let res = new Array(N).fill(0);
 
    // Traverse the array
    for(let i = 0;
            i < Bookings.length; i++)
    {
         
        // Store the first booked flight
        let l = Bookings[i][0];
 
        // Store the last booked flight
        let r = Bookings[i][1];
 
        // Store the total number of
        // seats booked in flights [l, r]
        let K = Bookings[i][2];
 
        // Add K to the flight L
        res[l - 1] = res[l - 1] + K;
 
        // Subtract K from flight
        // number R + 1
        if (r <= res.length - 1)
            res[r] = (-K) + res[r];
    }
 
    // Find the prefix sum of the array
    for(let i = 1; i < res.length; i++)
        res[i] = res[i] + res[i - 1];
 
    // Print the total number of seats
    // booked in each flight
    for(let i = 0; i < res.length; i++)
    {
        document.write(res[i] + " ");
    }
}
 
// Driver Code
 
// Given list of bookings
let bookings = [ [ 1, 3, 100 ],
                 [ 2, 6, 100 ],
                 [ 3, 4, 100 ] ];
let N = 6;
 
// Function Call
corpFlightBookings(bookings, N);
 
// This code is contributed by splevel62
 
</script>

Output

100 200 300 200 100 100

Time Complexity: O(N)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!