Dadas las horas de llegada y salida de todos los trenes que llegan a una estación de ferrocarril, la tarea es encontrar el número mínimo de andenes necesarios para la estación de ferrocarril para que ningún tren espere. Nos dan dos arrays que representan las horas de llegada y salida de los trenes que se detienen.
Ejemplos:
Input: arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}
dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}
Output: 3
Explanation: There are at-most three trains at a time (time between 9:40 to 12:00)
Input: arr[] = {9:00, 9:40}
dep[] = {9:10, 12:00}
Output: 1
Explanation: Only one platform is needed.
Enfoque ingenuo: la idea es tomar cada intervalo uno por uno y encontrar el número de intervalos que se superponen con él. Realice un seguimiento del número máximo de intervalos que se superponen con un intervalo. Finalmente, devuelve el valor máximo.
Siga los pasos que se mencionan a continuación:
- Ejecute dos bucles anidados, el bucle exterior de principio a fin y el bucle interior desde i+1 hasta el final.
- Para cada iteración del bucle externo, busque el recuento de intervalos que se cruzan con el intervalo actual.
- Actualice la respuesta con el recuento máximo de superposición en cada iteración del ciclo externo.
- Imprime la respuesta.
Implementación:
C++14
// C++ program to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number
// of platforms required
int findPlatform(int arr[], int dep[], int n)
{
// plat_needed indicates number of platforms
// needed at a time
int plat_needed = 1, result = 1;
int i = 1, j = 0;
// run a nested loop to find overlap
for (int i = 0; i < n; i++) {
// minimum platform
plat_needed = 1;
for (int j = i + 1; j < n; j++) {
// check for overlap
if (max(arr[i], arr[j]) <= min(dep[i], dep[j]))
plat_needed++;
}
// update result
result = max(result, plat_needed);
}
return result;
}
// Driver Code
int main()
{
int arr[] = { 9775, 494, 252, 1680 };
int dep[] = { 2052, 2254, 1395, 2130 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findPlatform(arr, dep, n);
return 0;
}
C
// C program to find minimum number of platforms required on
// a railway station
// Importing the required header files
#include <stdio.h>
// Creating MACRO for finding the maximum number
#define max(x, y) (((x) > (y)) ? (x) : (y))
// Creating MACRO for finding the minimum number
#define min(x, y) (((x) < (y)) ? (x) : (y))
// Function to returns the minimum number of platforms
// required
int findPlatform(int arr[], int dep[], int n)
{
// plat_needed indicates number of platforms
// needed at a time
int plat_needed = 1, result = 1;
int i = 1, j = 0;
// run a nested loop to find overlap
for (int i = 0; i < n; i++) {
// minimum platform
plat_needed = 1;
for (int j = i + 1; j < n; j++) {
// check for overlap
if (max(arr[i], arr[j]) <= min(dep[i], dep[j]))
plat_needed++;
}
// update result
result = max(result, plat_needed);
}
return result;
}
// Driver Code
int main()
{
int arr[] = { 900, 940, 950, 1100, 1500, 1800 };
int dep[] = { 910, 1200, 1120, 1130, 1900, 2000 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d", findPlatform(arr, dep, n));
return 0;
}
Python3
# Program to find minimum number of platforms
# required on a railway station
def findPlatform(arr, dep, n):
'''
Accepts two arrays with arrival and departure time
and the size of the array
Returns minimum number of platforms required
'''
# plat_needed indicates number of platforms
# needed at a time
plat_needed = 1
result = 1
# run a nested loop to find overlap
for i in range(n):
# minimum platform needed
plat_needed = 1
for j in range(i+1, n):
# check for overlap
if (max(arr[i], arr[j]) <= min(dep[i], dep[j])):
plat_needed += 1
# update result
result = max(result, plat_needed)
return result
# Driver code
def main():
arr = [900, 940, 950, 1100, 1500, 1800]
dep = [910, 1200, 1120, 1130, 1900, 2000]
n = len(arr)
print("{}".format(
findPlatform(arr, dep, n)))
if __name__ == '__main__':
main()
Java
// Program to find minimum number of platforms
// required on a railway station
import java.io.*;
class GFG {
// Returns minimum number of platforms required
public static int findPlatform(int arr[], int dep[],
int n)
{
// plat_needed indicates number of platforms
// needed at a time
int plat_needed = 1, result = 1;
int i = 1, j = 0;
// run a nested loop to find overlap
for (i = 0; i < n; i++) {
// minimum platform
plat_needed = 1;
for (j = i + 1; j < n; j++) {
// check for overlap
if (Math.max(arr[i], arr[j])
<= Math.min(dep[i], dep[j]))
plat_needed++;
}
// update result
result = Math.max(result, plat_needed);
}
return result;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 900, 940, 950, 1100, 1500, 1800 };
int dep[] = { 910, 1200, 1120, 1130, 1900, 2000 };
int n = 6;
System.out.println(findPlatform(arr, dep, n));
}
}
C#
// Program to find minimum number of platforms
// required on a railway station
using System;
public class GFG {
// Returns minimum number of platforms required
public static int findPlatform(int[] arr, int[] dep,
int n)
{
// plat_needed indicates number of platforms
// needed at a time
int plat_needed = 1, result = 1;
int i = 1, j = 0;
// run a nested loop to find overlap
for (i = 0; i < n; i++) {
// minimum platform
plat_needed = 1;
for (j = i + 1; j < n; j++) {
// check for overlap
if (Math.Max(arr[i], arr[j])
<= Math.Min(dep[i], dep[j]))
plat_needed++;
}
// update result
result = Math.Max(result, plat_needed);
}
return result;
}
// Driver Code
static public void Main()
{
int[] arr = { 900, 940, 950, 1100, 1500, 1800 };
int[] dep = { 910, 1200, 1120, 1130, 1900, 2000 };
int n = 6;
Console.WriteLine(findPlatform(arr, dep, n));
}
}
Javascript
<script>
// Program to find minimum number of platforms
// required on a railway station
function max(a,b)
{
if(a==b)
return a;
else{
if(a>b)
return a;
else
return b;
}
}
// Returns minimum number of platforms required
function findPlatform( arr, dep, n)
{
// plat_needed indicates number of platforms
// needed at a time
var plat_needed = 1, result = 1;
var i = 1, j = 0;
// run a nested loop to find overlap
for (var i = 0; i < n; i++) {
// minimum platform
plat_needed = 1;
for (var j = i + 1; j < n; j++) {
// check for overlap
if (max(arr[i], arr[j]) <= min(dep[i], dep[j]))
plat_needed++;
}
// update result
result = max(result, plat_needed);
}
return result;
}
var arr = [ 900, 940, 950, 1100, 1500, 1800 ];
var dep = [ 910, 1200, 1120, 1130, 1900, 2000 ];
var n =6;
document.write("Minimum Number of Platforms Required = "
+findPlatform(arr, dep, n));
</script>
Producción
3
Complejidad de tiempo: O (n 2 ), dos bucles anidados atraviesan la array.
Espacio auxiliar: O(1), ya que no se requiere espacio adicional.
Enfoque eficiente: almacene la hora de llegada y la hora de salida y ordénelas según la hora de llegada, luego verifique si la hora de llegada del siguiente tren es menor que la hora de salida del tren anterior, si es más pequeña, luego incremente el número de andenes necesarios de lo contrario no.
Siga los pasos que se mencionan a continuación:
- Almacene la hora de llegada y la hora de salida en la array arr y ordene esta array según la hora de llegada
- Declare una cola de prioridad (min-heap) y almacene la hora de salida del primer tren y también declare un contador cnt e inicialícelo con 1.
- Iterar sobre arr de 1 a n-1
- comprobar si la hora de llegada del tren actual es inferior o igual a la hora de salida del tren anterior que se mantiene en la parte superior de la cola de prioridad
- Si es verdadero, presione la nueva hora de salida e incremente el contador cnt
- de lo contrario, pop() la hora de salida
- empujar nueva hora de salida en la cola de prioridad
- comprobar si la hora de llegada del tren actual es inferior o igual a la hora de salida del tren anterior que se mantiene en la parte superior de la cola de prioridad
- Finalmente, devuelva el cnt .
C++
// C++ program to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number
// of platforms required
int findPlatform(int arr[], int dep[], int n)
{
// Store the arrival and departure time
vector<pair<int, int> > arr2(n);
for (int i = 0; i < n; i++) {
arr2[i] = { arr[i], dep[i] };
}
// Sort arr2 based on arrival time
sort(arr2.begin(), arr2.end());
priority_queue<int, vector<int>, greater<int> > p;
int count = 1;
p.push(arr2[0].second);
for (int i = 1; i < n; i++) {
// Check if arrival time of current train
// is less than or equals to departure time
// of previous train
if (p.top() >= arr2[i].first) {
count++;
}
else {
p.pop();
}
p.push(arr2[i].second);
}
// Return the number of train required
return count;
}
// Driver Code
int main()
{
int arr[] = { 900, 940, 950, 1100, 1500, 1800 };
int dep[] = { 910, 1200, 1120, 1130, 1900, 2000 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findPlatform(arr, dep, n);
return 0;
}
Producción
3
Complejidad de tiempo: O(N*log(N)) Espacio
auxiliar : O(N)
Otro enfoque eficiente: la idea es considerar todos los eventos en orden. Una vez que los eventos estén ordenados, rastree la cantidad de trenes en cualquier momento manteniendo un registro de los trenes que llegaron, pero que no partieron.
Ilustración:
arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}
dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}
All events are sorted by time.
Total platforms at any time can be obtained by
subtracting total departures from total arrivals
by that time.
Time Event Type Total Platforms Needed
at this Time
9:00 Arrival 1
9:10 Departure 0
9:40 Arrival 1
9:50 Arrival 2
11:00 Arrival 3
11:20 Departure 2
11:30 Departure 1
12:00 Departure 0
15:00 Arrival 1
18:00 Arrival 2
19:00 Departure 1
20:00 Departure 0
Minimum Platforms needed on railway station
= Maximum platforms needed at any time
= 3
Nota: Este enfoque supone que los trenes llegan y salen en la misma fecha.
Algoritmo:
- Ordenar los horarios de llegada y salida de los trenes.
- Cree dos punteros i = 0 y j = 0, y una variable para almacenar ans y cuenta actual plat
- Ejecute un ciclo while i<n y j<n y compare el i-ésimo elemento de la array de llegada y el j-ésimo elemento de la array de salida.
- Si la hora de llegada es inferior o igual a la de salida, se necesita una plataforma más, por lo que debe aumentar la cuenta, es decir, plat++ e incrementar i
- De lo contrario, si el tiempo de llegada es mayor que el de salida, se necesita una plataforma menos para disminuir el conteo, es decir, plat– e incrementar j
- Actualice ans, es decir, ans = max(ans, plat).
Implementación:
Esto no crea una única lista ordenada de todos los eventos, sino que clasifica individualmente las arrays arr[] y dep[], y luego utiliza el proceso de combinación de clasificación por combinación para procesarlas juntas como una única array ordenada.
C++
// Program to find minimum number of platforms
// required on a railway station
#include <algorithm>
#include <iostream>
using namespace std;
// Returns minimum number of platforms required
int findPlatform(int arr[], int dep[], int n)
{
// Sort arrival and departure arrays
sort(arr, arr + n);
sort(dep, dep + n);
// plat_needed indicates number of platforms
// needed at a time
int plat_needed = 1, result = 1;
int i = 1, j = 0;
// Similar to merge in merge sort to process
// all events in sorted order
while (i < n && j < n) {
// If next event in sorted order is arrival,
// increment count of platforms needed
if (arr[i] <= dep[j]) {
plat_needed++;
i++;
}
// Else decrement count of platforms needed
else if (arr[i] > dep[j]) {
plat_needed--;
j++;
}
// Update result if needed
if (plat_needed > result)
result = plat_needed;
}
return result;
}
// Driver code
int main()
{
int arr[] = { 900, 940, 950, 1100, 1500, 1800 };
int dep[] = { 910, 1200, 1120, 1130, 1900, 2000 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findPlatform(arr, dep, n);
return 0;
}
C
// C program to find minimum number of platforms required on a railway station
// Importing the required header files
#include <stdio.h>
#include <stdlib.h>
// Creating MACRO for finding the maximum number
#define max(x, y)(((x) > (y)) ? (x) : (y))
// Creating MACRO for finding the minimum number
#define min(x, y)(((x) < (y)) ? (x) : (y))
// below method is needed for the sort function
// compare function, compares two elements
int compare (const void * num1, const void * num2) {
if(*(int*)num1 > *(int*)num2)
return 1;
else
return -1;
}
// Returns minimum number of platforms required
int findPlatform(int arr[], int dep[], int n)
{
// Sort arrival and departure arrays
qsort(arr, n, sizeof(int), compare);
qsort(dep, n, sizeof(int), compare);
// plat_needed indicates number of platforms
// needed at a time
int plat_needed = 1, result = 1;
int i = 1, j = 0;
// Similar to merge in merge sort to process
// all events in sorted order
while (i < n && j < n) {
// If next event in sorted order is arrival,
// increment count of platforms needed
if (arr[i] <= dep[j]) {
plat_needed++;
i++;
}
// Else decrement count of platforms needed
else if (arr[i] > dep[j]) {
plat_needed--;
j++;
}
// Update result if needed
if (plat_needed > result)
result = plat_needed;
}
return result;
}
// Driver Code
int main()
{
int arr[] = { 900, 940, 950, 1100, 1500, 1800 };
int dep[] = { 910, 1200, 1120, 1130, 1900, 2000 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d", findPlatform(arr, dep, n));
return 0;
}
Java
// Program to find minimum number of platforms
import java.util.*;
class GFG {
// Returns minimum number of platforms required
static int findPlatform(int arr[], int dep[], int n)
{
// Sort arrival and departure arrays
Arrays.sort(arr);
Arrays.sort(dep);
// plat_needed indicates number of platforms
// needed at a time
int plat_needed = 1, result = 1;
int i = 1, j = 0;
// Similar to merge in merge sort to process
// all events in sorted order
while (i < n && j < n) {
// If next event in sorted order is arrival,
// increment count of platforms needed
if (arr[i] <= dep[j]) {
plat_needed++;
i++;
}
// Else decrement count of platforms needed
else if (arr[i] > dep[j]) {
plat_needed--;
j++;
}
// Update result if needed
if (plat_needed > result)
result = plat_needed;
}
return result;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 900, 940, 950, 1100, 1500, 1800 };
int dep[] = { 910, 1200, 1120, 1130, 1900, 2000 };
int n = arr.length;
System.out.println("Minimum Number of Platforms Required = "
+ findPlatform(arr, dep, n));
}
}
Python3
# Program to find minimum
# number of platforms
# required on a railway
# station
# Returns minimum number
# of platforms required
def findPlatform(arr, dep, n):
# Sort arrival and
# departure arrays
arr.sort()
dep.sort()
# plat_needed indicates
# number of platforms
# needed at a time
plat_needed = 1
result = 1
i = 1
j = 0
# Similar to merge in
# merge sort to process
# all events in sorted order
while (i < n and j < n):
# If next event in sorted
# order is arrival,
# increment count of
# platforms needed
if (arr[i] <= dep[j]):
plat_needed += 1
i += 1
# Else decrement count
# of platforms needed
elif (arr[i] > dep[j]):
plat_needed -= 1
j += 1
# Update result if needed
if (plat_needed > result):
result = plat_needed
return result
# Driver code
arr = [900, 940, 950, 1100, 1500, 1800]
dep = [910, 1200, 1120, 1130, 1900, 2000]
n = len(arr)
print("Minimum Number of Platforms Required = ",
findPlatform(arr, dep, n))
# This code is contributed
# by Anant Agarwal.
C#
// C# program to find minimum number
// of platforms
using System;
class GFG {
// Returns minimum number of platforms
// required
static int findPlatform(int[] arr, int[] dep, int n)
{
// Sort arrival and departure arrays
Array.Sort(arr);
Array.Sort(dep);
// plat_needed indicates number of
// platforms needed at a time
int plat_needed = 1, result = 1;
int i = 1, j = 0;
// Similar to merge in merge sort
// to process all events in sorted
// order
while (i < n && j < n) {
// If next event in sorted order
// is arrival, increment count
// of platforms needed
if (arr[i] <= dep[j])
{
plat_needed++;
i++;
}
// Else decrement count of
// platforms needed
else if (arr[i] > dep[j])
{
plat_needed--;
j++;
}
// Update result if needed
if (plat_needed > result)
result = plat_needed;
}
return result;
}
// Driver code
public static void Main()
{
int[] arr = { 900, 940, 950, 1100, 1500, 1800 };
int[] dep = { 910, 1200, 1120, 1130, 1900, 2000 };
int n = arr.Length;
Console.Write("Minimum Number of "
+ " Platforms Required = "
+ findPlatform(arr, dep, n));
}
}
// This code os contributed by nitin mittal.
PHP
<?php
// PHP Program to find minimum number
// of platforms required on a railway
// station
// Returns minimum number of
// platforms required
function findPlatform($arr, $dep, $n)
{
// Sort arrival and
// departure arrays
sort($arr);
sort($dep);
// plat_needed indicates
// number of platforms
// needed at a time
$plat_needed = 1;
$result = 1;
$i = 1;
$j = 0;
// Similar to merge in
// merge sort to process
// all events in sorted order
while ($i < $n and $j < $n)
{
// If next event in sorted
// order is arrival, increment
// count of platforms needed
if ($arr[$i] <= $dep[$j])
{
$plat_needed++;
$i++;
}
// Else decrement count
// of platforms needed
elseif ($arr[$i] > $dep[$j])
{
$plat_needed--;
$j++;
}
// Update result if needed
if ($plat_needed > $result)
$result = $plat_needed;
}
return $result;
}
// Driver Code
$arr = array(900, 940, 950, 1100, 1500, 1800);
$dep = array(910, 1200, 1120, 1130, 1900, 2000);
$n = count($arr);
echo "Minimum Number of Platforms Required = ", findPlatform($arr, $dep, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript Program to find minimum number
// of platforms required on a railway
// station
// Returns minimum number of
// platforms required
function findPlatform(arr, dep, n)
{
// Sort arrival and
// departure arrays
arr = arr.sort((a,b) => a-b));
dep = dep.sort((a,b) => a-b));
// plat_needed indicates
// number of platforms
// needed at a time
let plat_needed = 1;
let result = 1;
let i = 1;
let j = 0;
// Similar to merge in
// merge sort to process
// all events in sorted order
while (i < n && j < n)
{
// If next event in sorted
// order is arrival, increment
// count of platforms needed
if (arr[i] <= dep[j])
{
plat_needed++;
i++;
}
// Else decrement count
// of platforms needed
else if (arr[i] > dep[j])
{
plat_needed--;
j++;
}
// Update result if needed
if (plat_needed > result)
result = plat_needed;
}
return result;
}
// Driver Code
let arr = new Array(900, 940, 950, 1100, 1500, 1800);
let dep = new Array(910, 1200, 1120, 1130, 1900, 2000);
let n = arr.length;
document.write("Minimum Number of Platforms Required = " + findPlatform(arr, dep, n));
// This code is contributed by Saurabh Jaiswal.
</script>
Producción
3
Complejidad de tiempo: O (N * log N), se necesita un recorrido O (n) de ambos arreglos después de ordenar O (N * log N).
Espacio auxiliar: O(1), ya que no se requiere espacio adicional.
Nota: Hay un enfoque más para el problema, que usa O(n) espacio adicional y O(n) tiempo para resolver el problema:
Número mínimo de plataformas requeridas para una estación de tren/autobús | Conjunto 2 (enfoque basado en mapas)
Este artículo es una contribución de Shivam . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA