Número mínimo de andenes necesarios para una estación de tren/autobús | Conjunto 2 (enfoque basado en conjuntos)

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *