Dado un número entero N que indica el número de vuelos y la array de reservas[][3] con cada fila de la forma {a, b, K} que indica que hay K asientos reservados desde el vuelo a hasta el vuelo b (considere la indexación basada en 1) , la tarea es encontrar la secuencia del número de asientos reservados en N vuelos.
Ejemplos:
Entrada: reservas[][] = {{1, 2, 10}, {2, 3, 20}, {2, 5, 25}}
Salida: 10 55 45 25 25
Explicación:
Inicialmente, no hay asientos reservados en cualquiera de los vuelos. Entonces, la secuencia resultante es {0, 0, 0, 0, 0}
Reserve 10 asientos en los vuelos 1 a 2. La secuencia se convierte en {10, 10, 0, 0, 0}.
Reserve 20 asientos en los vuelos 2 a 3. La secuencia se convierte en {10, 30, 20, 0, 0}.
Reserve 25 asientos en los vuelos 2 a 5. La secuencia se convierte en {10, 55, 45, 25, 25}.Entrada: reservas[][] = {{1, 3, 100}, {2, 6, 100}, {3, 4, 100}}
Salida: 100 200 300 200 100 100
Enfoque ingenuo: siga los pasos a continuación para resolver el problema con el enfoque más simple posible:
- Inicialice una array seq[] de tamaño N para almacenar el recuento de asientos asignados en cada vuelo.
- Atraviesa la array reservas[] .
- Para cada consulta {a, b, K} , agregue el elemento K en la array seq[] del índice a a b .
- Después de completar los pasos anteriores, imprima la array seq[] como resultado.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar el concepto de suma de prefijos . Siga los pasos a continuación para resolver el problema:
- Inicialice una array seq[] de tamaño (N + 2) para almacenar todos los asientos asignados.
- Atraviesa la array reservas[] .
- Para cada consulta {a, b, K} , incremente la array seq[] en el índice (a – 1) en K y disminuya el elemento en el índice (b + 1) en K.
- Para la secuencia resultante, encuentre la suma del prefijo de la array seq[] .
- Después de completar los pasos anteriores, imprima la array seq[] como resultado.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
100 200 300 200 100 100
Complejidad temporal: O(N)
Espacio auxiliar: O(N)