Cuente el número máximo de autos estacionados al mismo tiempo

Posted on by Rudeus Greyrat

Dada una array 2d arr[][] con cada fila representando un par que representa el tiempo de entrada y salida de un automóvil en un estacionamiento, la tarea es calcular la cantidad máxima de automóviles que se pueden estacionar al mismo tiempo.

Ejemplos:

Entrada: arr[][] = {{1012, 1136}, {1317, 1417}, {1015, 1020}}
Salida: 2
Explicación:
el 1er auto entró a las 10:12 y sale a las 11:36 y el 3er auto entra a las 10:15 y sale a las 10:20.
Por lo tanto, el 1er y el 3er automóvil están presentes al mismo tiempo.

Entrada: arr[][] = {{1120, 1159}, {1508, 1529}, {1508, 1527}, {1503, 1600}, {1458, 1629}, {1224, 1313}}
Salida: 4
Explicación: Los coches 2º  , 3º , 4º y 5º están presentes al mismo tiempo.

Enfoque: La idea es utilizar el algoritmo de Kadane para resolver este problema. Siga los pasos a continuación para resolver el problema:

  • Inicialice un vector de pares para almacenar el tiempo de entrada o salida como el primer elemento de un par y true como el segundo elemento de un par, si el tiempo correspondiente almacenado es el tiempo de entrada. De lo contrario, guárdelo como falso.
  • Ordene el vector en orden de tiempo no decreciente .
  • Inicialice dos variables, digamos curMax , para buscar todos los segmentos contiguos verdaderos de la array, y maxFinal , para realizar un seguimiento del segmento contiguo verdadero más largo entre todos los segmentos verdaderos.
  • Iterar sobre el rango [0, 2*N – 1]:
    • Si ingresó un automóvil, incremente curMax en 1.
    • De lo contrario:
      • Si curMax > maxFinal , actualice maxFinal = curMax .
      • Cada vez que sale un automóvil, reste curMax por 1 .
  • Imprime maxFinal como la respuesta.

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 count maximum number
// of cars parked at the same
int maxCars(int arr[][2], int N)
{
    // Stores info about
    // entry and exit times
    pair<int, bool> a[2 * N];
 
    // Convert given array to new array
    for (int i = 0; i < N; i++) {
        a[2 * i] = { arr[i][0], true };
        a[2 * i + 1] = { arr[i][1], false };
    }
 
    // Sort array in ascending
    // order of time
    sort(a, a + 2 * N);
 
    // Stores current maximum
    // at every iteration
    int curMax = 0;
 
    // Stores final maximum number
    // of cars parked at any time
    int maxFinal = 0;
 
    // Traverse the array
    for (int i = 0; i < 2 * N; ++i) {
 
        // When car entered
        if (a[i].second) {
            curMax++;
        }
 
        // When car exits
        else {
            if (curMax > maxFinal) {
                maxFinal = curMax;
            }
            curMax--;
        }
    }
 
    // Print the answer
    cout << maxFinal;
}
 
// Driver Code
int main()
{
    // Given array
    int arr[][2] = { { 1012, 1136 },
                     { 1317, 1412 },
                     { 1015, 1020 } };
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    maxCars(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG{
 
// Pair class
static class pair
{
    int first;
    boolean second;
 
    pair(int first, boolean second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function to count maximum number
// of cars parked at the same
static void maxCars(int arr[][], int N)
{
     
    // Stores info about
    // entry and exit times
    pair a[] = new pair[2 * N];
 
    // Convert given array to new array
    for(int i = 0; i < N; i++)
    {
        a[2 * i] = new pair(arr[i][0], true);
        a[2 * i + 1] = new pair(arr[i][1], false);
    }
 
    // Sort array in ascending
    // order of time
    Arrays.sort(a, (p1, p2) -> p1.first - p2.first);
 
    // Stores current maximum
    // at every iteration
    int curMax = 0;
 
    // Stores final maximum number
    // of cars parked at any time
    int maxFinal = 0;
 
    // Traverse the array
    for(int i = 0; i < 2 * N; ++i)
    {
         
        // When car entered
        if (a[i].second)
        {
            curMax++;
        }
 
        // When car exits
        else
        {
            if (curMax > maxFinal)
            {
                maxFinal = curMax;
            }
            curMax--;
        }
    }
 
    // Print the answer
    System.out.println(maxFinal);
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given array
    int arr[][] = { { 1012, 1136 },
                    { 1317, 1412 },
                    { 1015, 1020 } };
 
    // Size of the array
    int N = arr.length;
 
    // Function Call
    maxCars(arr, N);
}
}
 
// This code is contributed by Kingash

Python3

# Python3 program for the above approach
 
# Function to count maximum number
# of cars parked at the same
def maxCars(arr, N):
   
    # Stores info about
    # entry and exit times
    a = [[0,True] for i in range(2 * N)]
 
    # Convert given array to new array
    for i in range(N):
        a[2 * i] = [arr[i][0], True]
        a[2 * i + 1] = [arr[i][1], False]
 
    # Sort array in ascending
    # order of time
    a = sorted(a)
 
    # Stores current maximum
    # at every iteration
    curMax = 0
 
    # Stores final maximum number
    # of cars parked at any time
    maxFinal = 0
 
    # Traverse the array
    for i in range(2*N):
 
        # When car entered
        if (a[i][1]):
            curMax += 1
        # When car exits
        else:
            if (curMax > maxFinal):
                maxFinal = curMax
            curMax -= 1
 
    # Print answer
    print (maxFinal)
 
# Driver Code
if __name__ == '__main__':
    # Given array
    arr= [ [ 1012, 1136 ],
         [ 1317, 1412 ],
         [ 1015, 1020 ]]
 
    # Size of the array
    N = len(arr)
 
    # Function Call
    maxCars(arr, N)
 
# This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
class GFG
{
    // Function to count maximum number
    // of cars parked at the same
    static void maxCars(int[,] arr, int N)
    {
       
        // Stores info about
        // entry and exit times
        Tuple<int, bool>[] a = new Tuple<int, bool>[2 * N];
      
        // Convert given array to new array
        for (int i = 0; i < N; i++) {
            a[2 * i] = new Tuple<int, bool>(arr[i,0], true);
            a[2 * i + 1] = new Tuple<int, bool>(arr[i,1], false);
        }
      
        // Stores current maximum
        // at every iteration
        int curMax = 1;
      
        // Stores final maximum number
        // of cars parked at any time
        int maxFinal = 0;
      
        // Traverse the array
        for (int i = 0; i < 2 * N; ++i) {
      
            // When car entered
            if (a[i].Item2) {
                curMax++;
            }
      
            // When car exits
            else {
                if (curMax > maxFinal) {
                    maxFinal = curMax;
                }
                curMax--;
            }
        }
      
        // Print the answer
        Console.WriteLine(maxFinal);
    }
 
  static void Main ()
  {
    // Given array
    int[,] arr = { { 1012, 1136 },
                    { 1317, 1412 },
                    { 1015, 1020 } };
  
    // Size of the array
    int N = 2;
  
    // Function Call
    maxCars(arr, N);
  }
}
 
// This code is contributed by suresh07.

Javascript

<script>
 
// JavaScript program for the above approach
 
// Pair class
class pair
{
    constructor(first,second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function to count maximum number
// of cars parked at the same
function maxCars(arr,N)
{
    // Stores info about
    // entry and exit times
    let a = new Array(2 * N);
  
    // Convert given array to new array
    for(let i = 0; i < N; i++)
    {
        a[2 * i] = new pair(arr[i][0], true);
        a[2 * i + 1] = new pair(arr[i][1], false);
    }
  
    // Sort array in ascending
    // order of time
    a.sort(function(p1, p2){return p1.first - p2.first});
  
    // Stores current maximum
    // at every iteration
    let curMax = 0;
  
    // Stores final maximum number
    // of cars parked at any time
    let maxFinal = 0;
  
    // Traverse the array
    for(let i = 0; i < 2 * N; ++i)
    {
          
        // When car entered
        if (a[i].second)
        {
            curMax++;
        }
  
        // When car exits
        else
        {
            if (curMax > maxFinal)
            {
                maxFinal = curMax;
            }
            curMax--;
        }
    }
  
    // Print the answer
    document.write(maxFinal+"<br>");
}
 
// Driver Code
let arr=[[ 1012, 1136 ],
                    [ 1317, 1412 ],
                    [ 1015, 1020 ]];
// Size of the array
let N = arr.length;
 
// Function Call
maxCars(arr, N);
 
 
// This code is contributed by unknown2108
 
</script>
Producción: 

2

 

Complejidad temporal: O(NLogN)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por sam_2200 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 *