Dadas las horas de llegada y salida de todos los trenes que llegan a una estación de ferrocarril, encuentre el número mínimo de plataformas requeridas para la estación de ferrocarril para que ningún tren espere. Tenemos 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
There are at-most three trains at a time
(time between 11:00 to 11:20)
Ya hemos discutido sus soluciones simples y basadas en clasificación en la publicación a continuación.
Número mínimo de plataformas requeridas para una estación de tren/autobús .
En esta publicación, estamos insertando todos los tiempos de llegada y salida en un conjunto múltiple . El primer valor del elemento en multiset indica la hora de llegada/salida y el segundo valor indica si es la llegada o la salida representada por ‘a’ o ‘d’ respectivamente.
Si llega, incremente en 1; de lo contrario, disminuya el valor en 1. Si estamos tomando la entrada de STDIN, podemos insertar directamente los tiempos en el conjunto múltiple y no es necesario almacenar los tiempos en la array.
Implementación:
C++
// C++ program to find minimum number of platforms
// required on a railway station
#include <bits/stdc++.h>
using namespace std;
int findPlatform(int arr[], int dep[], int n)
{
// Insert all the times (arr. and dep.)
// in the multiset.
multiset<pair<int, char> > order;
for (int i = 0; i < n; i++) {
// If its arrival then second value
// of pair is 'a' else 'd'
order.insert(make_pair(arr[i], 'a'));
order.insert(make_pair(dep[i], 'd'));
}
int result = 0;
int plat_needed = 0;
// Start iterating the multiset.
for (auto it : order) {
// If its 'a' then add 1 to plat_needed
// else minus 1 from plat_needed.
if (it.second == 'a')
plat_needed++;
else
plat_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 << "Minimum Number of Platforms Required = "
<< findPlatform(arr, dep, n);
return 0;
}
Java
// Java program to find minimum number
// of platforms required on a railway station
import java.io.*;
import java.util.*;
class pair
{
int first;
char second;
pair(int key1, char key2)
{
this.first = key1;
this.second = key2;
}
}
class GFG{
public static int findPlatform(int arr[], int dep[],
int n)
{
// Insert all the times (arr. and dep.)
// in the ArrayList of pairs.
ArrayList<pair> order = new ArrayList<>();
for(int i = 0; i < n; i++)
{
order.add(new pair(arr[i], 'a'));
order.add(new pair(dep[i], 'd'));
}
// Custom sort order ArrayList, first
// by time than by arrival or departure
Collections.sort(order, new Comparator<pair>()
{
public int compare(pair p1, pair p2)
{
if (p1.first == p2.first)
return new Character(p1.second)
.compareTo(
new Character(p2.second));
return p1.first - p2.first;
}
});
int result = 1;
int plat_needed = 0;
for(int i = 0; i < order.size(); i++)
{
pair p = order.get(i);
// If its 'a' then add 1 to plat_needed
// else minus 1 from plat_needed.
if (p.second == 'a')
plat_needed++;
else
plat_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 = 6;
System.out.println("Minimum Number of " +
"Platforms Required = " +
findPlatform(arr, dep, n));
}
}
// This code is contributed by RohitOberoi
Python3
# Python3 program to find minimum number
# of platforms required on a railway station
def findPlatform(arr, dep, n):
# Inserting all the arr. and dep. times
# in the array times
times = []
for i in range(n):
times.append([dep[i], 'd'])
times.append([arr[i], 'a'])
# Sort the array
times = sorted(times, key = lambda x: x[1])
times = sorted(times, key = lambda x: x[0])
result, plat_needed = 0, 0
for i in range(2 * n):
# If its 'a' then add 1 to plat_needed
# else minus 1 from plat_needed.
if times[i][1] == 'a':
plat_needed += 1
result = max(plat_needed, result)
else:
plat_needed -= 1
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 Tharun Reddy
C#
// C# program to find minimum number
// of platforms required on a railway station
using System;
using System.Collections.Generic;
public class pair {
public int first;
public char second;
public pair(int key1, char key2) {
this.first = key1;
this.second = key2;
}
}
public class GFG {
public static int findPlatform(int []arr, int []dep, int n) {
// Insert all the times (arr. and dep.)
// in the List of pairs.
List<pair> order = new List<pair>();
for (int i = 0; i < n; i++) {
order.Add(new pair(arr[i], 'a'));
order.Add(new pair(dep[i], 'd'));
}
// Custom sort order List, first
// by time than by arrival or departure
order.Sort((p1,p2)=> p1.first == p2.first? p1.second -
p2.second: p1.first - p2.first);
int result = 1;
int plat_needed = 0;
for (int i = 0; i < order.Count; i++) {
pair p = order[i];
// If its 'a' then add 1 to plat_needed
// else minus 1 from plat_needed.
if (p.second == 'a')
plat_needed++;
else
plat_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 = 6;
Console.WriteLine("Minimum Number of " +
"Platforms Required = " +
findPlatform(arr, dep, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to find minimum number of platforms
// required on a railway station
const findPlatform = (arr, dep, n) => {
// Insert all the times (arr. and dep.)
// in the multiset.
let order = new Set();
for (let i = 0; i < n; i++) {
// If its arrival then second value
// of pair is 'a' else 'd'
order.add([arr[i], 'a']);
order.add([dep[i], 'd']);
}
let result = 0;
let plat_needed = 0;
order = [...order];
order = order.sort((a, b) => a[0] - b[0])
// Start iterating the multiset.
for (let it in order) {
// If its 'a' then add 1 to plat_needed
// else minus 1 from plat_needed.
if (order[it][1] == 'a')
plat_needed++;
else
plat_needed--;
if (plat_needed > result)
result = plat_needed;
}
return result;
}
// Driver code
let arr = [900, 940, 950, 1100, 1500, 1800];
let dep = [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 rakeshsahni
</script>
Producción
Minimum Number of Platforms Required = 3
Análisis de Complejidad:
- Complejidad temporal: O( N* LogN).
Dado que estamos insertando en multiset y mantiene elementos en orden ordenado. Entonces, las operaciones de inserción N en conjuntos múltiples requieren una complejidad de tiempo N * LogN.
- Complejidad espacial: O(N).
Estamos usando multiset que tendrá 2*N elementos.
Implementación:
C++
// C++ program to find minimum number of platforms
// required on a railway station
#include <bits/stdc++.h>
using namespace std;
int minPlatform(int arrival[], int departure[], int n)
{
// as time range from 0 to 2359 in 24 hour clock,
// we declare an array for values from 0 to 2360
int platform[2361] = {0};
int requiredPlatform = 1;
for (int i = 0; i < n; i++) {
// increment the platforms for arrival
++platform[arrival[i]];
// once train departs we decrease the platform count
--platform[departure[i] + 1];
}
// We are running loop till 2361 because maximum time value
// in a day can be 23:60
for (int i = 1; i < 2361; i++) {
// taking cumulative sum of platform give us required
// number of platform for every minute
platform[i] = platform[i] + platform[i - 1];
requiredPlatform = max(requiredPlatform, platform[i]);
}
return requiredPlatform;
}
// 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 << "Minimum Number of Platforms Required = "
<< minPlatform(arr, dep, n);
return 0;
}
Java
// Java program to find minimum number
// of platforms required on a railway
// station
import java.util.*;
import java.lang.*;
class GFG{
static int minPlatform(int arrival[],
int departure[],
int n)
{
// As time range from 0 to 2359 in
// 24 hour clock, we declare an array
// for values from 0 to 2360
int[] platform = new int[2361];
int requiredPlatform = 1;
for(int i = 0; i < n; i++)
{
// Increment the platforms for arrival
++platform[arrival[i]];
// Once train departs we decrease
// the platform count
--platform[departure[i] + 1];
}
// We are running loop till 2361 because
// maximum time value in a day can be 23:60
for(int i = 1; i < 2361; i++)
{
// Taking cumulative sum of platform
// give us required number of
// platform for every minute
platform[i] = platform[i] +
platform[i - 1];
requiredPlatform = Math.max(requiredPlatform,
platform[i]);
}
return requiredPlatform;
}
// 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 = " +
minPlatform(arr, dep, n));
}
}
// This code is contributed by offbeat
Python3
# Python3 program to find minimum number
# of platforms required on a railway station
def minPlatform(arrival, departure, n):
# As time range from 0 to 2359 in
# 24 hour clock, we declare an array
# for values from 0 to 2360
platform = [0] * 2361
requiredPlatform = 1
for i in range(n):
# Increment the platforms for arrival
platform[arrival[i]] += 1
# Once train departs we decrease the
# platform count
platform[departure[i] + 1] -= 1
# We are running loop till 2361 because
# maximum time value in a day can be 23:60
for i in range(1, 2361):
# Taking cumulative sum of
# platform give us required
# number of platform for every minute
platform[i] = platform[i] + platform[i - 1]
requiredPlatform = max(requiredPlatform,
platform[i])
return requiredPlatform
# 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 = ",
minPlatform(arr, dep, n))
# This code is contributed by PawanJain1
C#
// C# program to find minimum number
// of platforms required on a railway
// station
using System;
class GFG {
static int minPlatform(int[] arrival, int[] departure, int n)
{
// As time range from 0 to 2359 in
// 24 hour clock, we declare an array
// for values from 0 to 2360
int[] platform = new int[2361];
int requiredPlatform = 1;
for(int i = 0; i < n; i++)
{
// Increment the platforms for arrival
++platform[arrival[i]];
// Once train departs we decrease
// the platform count
--platform[departure[i] + 1];
}
// We are running loop till 2361 because
// maximum time value in a day can be 23:60
for(int i = 1; i < 2361; i++)
{
// Taking cumulative sum of platform
// give us required number of
// platform for every minute
platform[i] = platform[i] +
platform[i - 1];
requiredPlatform = Math.Max(requiredPlatform,
platform[i]);
}
return requiredPlatform;
}
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 = " +
minPlatform(arr, dep, n));
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// JavaScript program for the above approach
function minPlatform(arrival, departure, n) {
// as time range from 0 to 2359 in 24 hour clock,
// we declare an array for values from 0 to 2360
let platform = new Array(2361).fill(0);
let requiredPlatform = 1;
for (let i = 0; i < n; i++) {
// increment the platforms for arrival
++platform[arrival[i]];
// once train departs we
// decrease the platform count
--platform[departure[i] + 1];
}
// We are running loop till 2361
// because maximum time value
// in a day can be 23:60
for (let i = 1; i < 2361; i++) {
// taking cumulative sum of
// platform give us required
// number of platform for every minute
platform[i] =
platform[i] + platform[i - 1];
requiredPlatform =
Math.max(requiredPlatform, platform[i]);
}
return requiredPlatform;
}
// Driver code
let arr = [900, 940, 950, 1100, 1500, 1800];
let dep = [910, 1200, 1120, 1130, 1900, 2000];
let n = arr.length;
document.write("Minimum Number of Platforms Required = "
+ minPlatform(arr, dep, n));
// This code is contributed by Potta Lokesh
</script>
Producción
Minimum Number of Platforms Required = 3
Análisis de Complejidad:
- Complejidad temporal: O(N).
- Complejidad espacial: O(1).
Este artículo es una contribución de Jatin Goyal y Abhinav Kumar Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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