Dada una array 2D arr[][3] que consta de información de N trenes, donde arr[i][0] es el número de tren, arr[i][1] es la hora de llegada y arr[i][2] es la duración del tiempo de parada. Dado otro entero F que representa el número de tren, la tarea es encontrar el número de plataforma en el que llega el tren con el número de tren F de acuerdo con las siguientes reglas:
- La numeración de plataformas comienza desde 1 y hay un número infinito de plataformas.
- La plataforma que se libera antes se asigna al siguiente tren.
- Si se liberan dos o más andenes al mismo tiempo, el tren llega al andén con el número de andén más bajo.
- Si dos o más trenes llegan al mismo tiempo, entonces el tren con un número de tren más pequeño se asigna primero.
Ejemplos:
Entrada: arr[] = {{112567, 1, 2}, {112563, 3, 3}, {112569, 4, 7}, {112560, 9, 3}}, F = 112569
Salida: 1
Explicación:
A continuación se muestra el orden de llegada de los trenes: Hora de salida de
la plataforma del tren
112567 1 4
112563 2 7
112569 1 12
112560 2 13Por tanto, el tren con el número de tren 112569 llega al andén número 1.
Entrada: arr[] = {{112567, 2, 1}, {112563, 5, 5}, {112569, 7, 3}, {112560, 3, 7}}, F = 112569
Salida: 3
Enfoque: el problema dado se puede resolver utilizando la cola de prioridad . Siga los pasos a continuación para resolver este problema:
- Ordene la array dada arr[] de N trenes según la hora de llegada de los trenes.
- Inicialice una cola de prioridad , digamos PQ de pares {PlatformNumber, time} que implementa el montón mínimo de acuerdo con el tiempo de salida mínimo. Inserte el {número de plataforma, hora} , es decir, {1, 0} en la cola de prioridad.
- Inicialice un HashMap , digamos M que almacena el número de plataforma en el que llega cualquier tren.
- Recorra la array dada arr[] y realice los siguientes pasos:
- Abre la plataforma superior del PQ y guárdalos en free_platform[] .
- Si la hora de llegada del tren actual es al menos la hora de salida del andén abierto, actualice la hora de salida del andén abierto como (suma de la hora de llegada y parada + 1) e inserte el estado actual del andén en PQ y el número de plataforma actual del tren actual en el HashMap M.
- De lo contrario, agregue la nueva entrada de plataforma al PQ y el número de plataforma actual del tren actual en el HashMap M.
- Después de completar los pasos anteriores, imprima el número de plataforma asociado con el número de tren F en el HashMap M.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program for the above approach
import java.util.*;
// Stores the information for each
// train as Objects
class Train {
// Stores the train number
String train_num;
// Stores the arrival time
int arrival_time;
// Stores the stoppage time
int stoppage_time;
// Constructor
Train(String train_num,
int arrival_time,
int stoppage_time)
{
this.train_num = train_num;
this.arrival_time = arrival_time;
this.stoppage_time = stoppage_time;
}
}
public class GFG {
// Function to find the platform
// on which train F arrives
static int findPlatformOf(
ArrayList<Train> trains, int n,
String F)
{
// Sort the array arr[] according
// to the arrival time
Collections.sort(
trains,
(a, b) -> a.arrival_time==b.arrival_time ? Integer.parseInt(a.train_num)-Integer.parseInt(b.train_num) : a.arrival_time - b.arrival_time);
// Stores the platforms that
// is in currently in use
PriorityQueue<int[]> pq
= new PriorityQueue<>(
(a, b)
-> a[1] == b[1] ? a[0] - b[0]
: a[1] - b[1]);
// Insert the platform number 1
// with departure time as 0
pq.add(new int[] { 1, 0 });
// Store the platform number
// on which train arrived
HashMap<String, Integer> schedule
= new HashMap<>();
// Traverse the given array
for (Train t : trains) {
// Pop the top platform of
// the priority queue
int[] free_platform = pq.poll();
// If arrival time of the train
// >= freeing time of the platform
if (t.arrival_time >= free_platform[1]) {
// Update the train status
free_platform[1]
= t.arrival_time + t.stoppage_time + 1;
// Add the current platform
// to the pq
pq.add(free_platform);
// Add the platform
// number to the HashMap
schedule.put(t.train_num,
free_platform[0]);
}
// Otherwise, add a new platform
// for the current train
else {
// Update the priority queue
pq.add(free_platform);
// Get the platform number
int platform_num = pq.size() + 1;
// Add the platform to
// the priority queue
pq.add(new int[] {
platform_num,
t.arrival_time
+ t.stoppage_time + 1 });
// Add the platform
// number to the HashMap
schedule.put(t.train_num,
platform_num);
}
}
// Return the platform on
// which F train arrived
return schedule.get(F);
}
// Driver Code
public static void main(String[] args)
{
ArrayList<Train> trains
= new ArrayList<>();
trains.add(new Train(
"112567", 2, 1));
trains.add(new Train(
"112569", 5, 5));
trains.add(new Train(
"112563", 5, 3));
trains.add(new Train(
"112560", 3, 7));
String F = "112563";
System.out.println(
findPlatformOf(
trains, trains.size(), F));
}
}
3
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA