Dada una string S que representa el registro de los trabajadores que ingresan y salen del área de descanso, donde E representa el ingreso y la L representa la salida del área de descanso. Para cada trabajador, se requiere una silla. La tarea es encontrar el número mínimo de sillas necesarias para que no haya escasez de sillas en un momento dado.
Ejemplos:
Entrada: S = “EELEE”
Salida: 3
Explicación:
Paso 1: Entra una persona. Por lo tanto, se requiere 1 silla por ahora.
Paso 2: Entra otra persona. Por lo tanto, se requiere aumentar el número de sillas a 2.
Paso 3: Una persona se va. Por lo tanto, no es necesario aumentar el número de sillas.
Paso 4: Entra otra persona. Aún así, no es necesario aumentar el número de sillas.
Paso 4: Entra otra persona. Por lo tanto, se necesita aumentar el número de sillas a 3.
Por lo tanto, se requiere un mínimo de 3 sillas para que nunca haya escasez de sillas.Entrada: S = “EL”
Salida: 1
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicializar una variable, digamos, contar .
- Itere sobre los caracteres de la string usando una variable, digamos i .
- Si el i -ésimo carácter es ‘E’ , aumente la cuenta en 1 , ya que se requieren más sillas.
- Si el i -ésimo carácter es ‘L’ , entonces disminuya el conteo en 1 a medida que se vacía una de las sillas.
- Imprime el valor máximo de conteo obtenido en cualquier paso.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number
// of chairs required to ensure that
// every worker is seated at any time
int findMinimumChairs(string s)
{
// Stores the number of
// chairs required
int count = 0;
// Pointer to iterate
int i = 0;
// Stores minimum number of
// chairs required
int mini = INT_MIN;
// Iterate over every character
while (i < s.length()) {
// If character is 'E'
if (s[i] == 'E')
// Increase the count
count++;
// Otherwise
else
count--;
// Update maximum value of count
// obtained at any given time
mini = max(count, mini);
i++;
}
// Return mini
return mini;
}
// Driver Code
int main()
{
// Input
// Given String
string s = "EELEE";
// Function call to find the
// minimum number of chairs
cout << findMinimumChairs(s);
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to find the minimum number
// of chairs required to ensure that
// every worker is seated at any time
static int findMinimumChairs(String s)
{
// Stores the number of
// chairs required
int count = 0;
// Pointer to iterate
int i = 0;
// Stores minimum number of
// chairs required
int mini = Integer.MIN_VALUE;
// Iterate over every character
while (i < s.length()) {
// If character is 'E'
if (s.charAt(i) == 'E')
// Increase the count
count++;
// Otherwise
else
count--;
// Update maximum value of count
// obtained at any given time
mini = Math.max(count, mini);
i++;
}
// Return mini
return mini;
}
// Driver code
public static void main(String[] args)
{
// Input
// Given String
String s = "EELEE";
// Function call to find the
// minimum number of chairs
System.out.print(findMinimumChairs(s));
}
}
// This code is contributed by code_hunt.
Python3
# Python 3 implementation of # the above approach import sys # Function to find the minimum number # of chairs required to ensure that # every worker is seated at any time def findMinimumChairs(s): # Stores the number of # chairs required count = 0 # Pointer to iterate i = 0 # Stores minimum number of # chairs required mini = -sys.maxsize - 1 # Iterate over every character while (i < len(s)): # If character is 'E' if (s[i] == 'E'): # Increase the count count += 1 # Otherwise else: count -= 1 # Update maximum value of count # obtained at any given time mini = max(count, mini) i += 1 # Return mini return mini # Driver Code if __name__ == '__main__': # Input # Given String s = "EELEE" # Function call to find the # minimum number of chairs print(findMinimumChairs(s)) # This code is contributed by ipg2016107.
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the minimum number
// of chairs required to ensure that
// every worker is seated at any time
static int findMinimumChairs(string s)
{
// Stores the number of
// chairs required
int count = 0;
// Pointer to iterate
int i = 0;
// Stores minimum number of
// chairs required
int mini = Int32.MinValue;
// Iterate over every character
while (i < s.Length) {
// If character is 'E'
if (s[i] == 'E')
// Increase the count
count++;
// Otherwise
else
count--;
// Update maximum value of count
// obtained at any given time
mini = Math.Max(count, mini);
i++;
}
// Return mini
return mini;
}
// Driver code
public static void Main()
{
// Input
// Given String
string s = "EELEE";
// Function call to find the
// minimum number of chairs
Console.WriteLine(findMinimumChairs(s));
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// Javascript implementation of
// the above approach
// Function to find the minimum number
// of chairs required to ensure that
// every worker is seated at any time
function findMinimumChairs(s)
{
// Stores the number of
// chairs required
var count = 0;
// Pointer to iterate
var i = 0;
// Stores minimum number of
// chairs required
var mini = -2147483647;
// Iterate over every character
while (i < s.length) {
// If character is 'E'
if (s[i] == 'E')
// Increase the count
count++;
// Otherwise
else
count--;
// Update maximum value of count
// obtained at any given time
mini = Math.max(count, mini);
i++;
}
// Return mini
return mini;
}
// Driver Code
// Input
// Given String
var s = "EELEE";
// Function call to find the
// minimum number of chairs
document.write(findMinimumChairs(s));
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)