Encuentra Mínimo y Máximo de personas distintas entrando o saliendo de la habitación

Dada una string binaria de personas donde ‘1’ y ‘0’ representan personas entrando y saliendo de una habitación respectivamente. La tarea es encontrar las personas distintas mínimas y máximas que entran o salen del edificio.

Ejemplos:

Entrada: “000”
Salida: Mínimo de personas: 3
Máximo de personas: 3
Explicación: 3 personas distintas abandonaron el edificio.

Entrada: “111”
Salida: Mínimo de personas: 3
Máximo de personas: 3
Explicación: 3 personas distintas entraron al edificio.

Entrada: “110011”
Salida: Mínimo de personas: 2
Máximo de personas: 6
Explicación: 2 personas ingresadas->esas 2 personas restantes->las mismas 2 personas ingresadas 
para dar cuenta de un mínimo de 2 personas.
Todas las personas que ingresan o salen son distintas para contar con un máximo de 6 personas.

Entrada: “10101”
Salida: Mínimo de personas: 1
Máximo de personas: 5
Explicación:  1 persona ingresó- > se fue -> nuevamente ingresó -> nuevamente se fue -> y nuevamente ingresó 
para contabilizar mínimo 1 persona.
Todas las personas que entran o salen son distintas para contabilizar un máximo de 5 personas.

Enfoque : El problema se puede resolver en base a la siguiente observación:

• Cada persona que entra o sale de la habitación puede ser una persona única. Esto le dará el número máximo de personas que pueden entrar en una habitación. Será igual al número total de veces que se realice una operación de salida o entrada,
• Cada vez, las mismas personas que salen de la habitación entran a la habitación la próxima vez. Entonces, el máximo entre las personas que salen a la vez o entran a la vez es el mínimo número posible de personas únicas.

Siga la siguiente ilustración para una mejor comprensión.

Ilustración:

Considere personas = “10101”

Para encontrar el máximo :

        => Al principio, la primera persona (digamos P1) entra en la habitación
        => Luego, la segunda persona (digamos P2) sale de la habitación
        => Luego, la tercera persona (digamos P3) ingresa a la habitación
        => Luego, la cuarta persona (digamos P4) sale de la habitación
        => Por fin, la quinta persona (digamos P5) entra en la habitación

Total 5 personas entran o salen de la habitación como máximo.

Para encontrar el mínimo de personas posibles:

        => Al principio, la primera persona (por ejemplo, P1) entra en la habitación.
        => Entonces P1 sale de la habitación.
        => Entonces P1 vuelve a entrar en la habitación.
        => Entonces nuevamente P1 sale de la habitación.
        => Por fin P1 vuelve a entrar en la habitación.

Entonces al menos una persona entra o sale de la habitación.

Siga los pasos a continuación para implementar la observación anterior:

• Comience a atravesar toda la string de personas .
• Si personas[i] = ‘1’ , entonces se ingresó el incremento ; de lo contrario, se ingresó el decremento .
• Almacene el valor máximo de ingresado y N (tamaño de la string de personas) como el primer y segundo valor del resultado del par .
• En ese ciclo, si en cualquier momento ingresado se vuelve negativo, reinícielo a 0 e incremente el primer valor del resultado del par .
• Devuelve el resultado como el par final que contiene el mínimo y el máximo de personas distintas como primer y segundo valor respectivamente.

A continuación se muestra la implementación del enfoque anterior:

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum and
// maximum number of possible persons
// entering or leaving the room
pair<int,int> minDistPersons(string& persons)
{
   int N=persons.length(),entered=0;
   pair<int,int>result={0,N};
    
   for(int i=0;i<N;i++)
   {
       if(persons[i]=='1')
       entered++;
       else entered--;
        
       result.first=max(result.first,entered);
        
       if(entered<0)
       {
         entered=0;
           result.first++;
       }
   }
    
   return result;
}
 
// Driver code
int main()
{
    string persons = "10101";
 
    // Function call
    pair<int, int> ans = minDistPersons(persons);
    cout << "Minimum Persons: " << ans.first
         << "\n";
    cout << "Maximum Persons: " << ans.second;
    return 0;
}
// this code is contributed by prophet1999

// Java code to implement the approach
import java.io.*;
 
class GFG
{
 
  // Function to find the minimum and
  // maximum number of possible persons
  // entering or leaving the room
  public static int[] minDistPersons(String persons)
  {
    int N = persons.length();
    int entered = 0;
    int result[] = new int[2];
    result[1] = N;
    for (int i = 0; i < N; i++) {
         
      if (persons.charAt(i) == '1')
        entered++;
      else entered--;
       
      result[0] = Math.max(result[0],entered);
       
      if(entered<0)
      {
          entered=0;
          result[0]++;
      }
       
    }
 
    return result;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    String persons = "10101";
 
    // Function call
    int ans[] = minDistPersons(persons);
    System.out.println("Minimum Persons: " + ans[0]);
    System.out.print("Maximum Persons: " + ans[1]);
  }
}
 
// this code is contributed by prophet1999

# Python3 code for the above approach
 
# Function to find the minimum and
# maximum number of positive persons
# entering or leaving the room
def minDistPersons(persons):
    N = len(persons)
    entered, exited = 0, 0
    result = [0, N]
 
    for i in range(N):
        if persons[i] == "1":
            entered+=1
        else:
            entered-=1
        result[0] = max(result[0], entered)
        if(entered<0):
            entered=0
            result[0]+=1
 
    return result
 
# Driver Code
persons = "10101"
 
# Function call
ans = minDistPersons(persons)
 
print("Minimum Persons: " + str(ans[0]))
print("Maximum Persons: " + str(ans[1]))
 
# this code is contributed by prophet1999

// C# program for above approach
using System;
class GFG
{
 
   
  // Function to find the minimum and
  // maximum number of possible persons
  // entering or leaving the room
  public static int[] minDistPersons(string persons)
  {
    int N = persons.Length;
    int entered = 0;
    int[] result = new int[2];
    result[1] = N;
    for (int i = 0; i < N; i++) {
         
      if (persons[i] == '1')
        entered++;
      else entered--;
       
      result[0] = Math.Max(result[0],entered);
       
      if(entered<0)
      {
          entered=0;
          result[0]++;
      }
       
    }
 
    return result;
  }
 
// Driver Code
public static void Main()
{
    string persons = "10101";
 
    // Function call
    int[] ans = minDistPersons(persons);
    Console.WriteLine("Minimum Persons: " + ans[0]);
    Console.Write("Maximum Persons: " + ans[1]);
}
}
 
// This code is contributed by code_hunt.

<script>
       // JavaScript code for the above approach
 
       // Function to find the minimum and
       // maximum number of possible persons
       // entering or leaving the room
       function minDistPersons(persons) {
           let N = persons.length;
           let entered = 0;
           let result = [0, N];
 
           for (let i = 0; i < N; i++) {
               if (persons[i] == '1')
                   entered++;
               else
                   entered--;
                    
               result[0] = Math.max(...[result[0], entered]);
                
               if(entered<0)
               {
                   entered=0;
                   result[0]++;
               }
           }
 
           return result;
       }
 
       // Driver code
       let persons = "10101";
 
       // Function call
       let ans = minDistPersons(persons);
       document.write("Minimum Persons: " + ans[0] + '<br>');
       document.write("Maximum Persons: " + ans[1]);
 
   // this code is contributed by prophet1999
   </script>

Minimum Persons: 1
Maximum Persons: 5

Complejidad de tiempo: O(N), donde N es la longitud de la string de personas .
Espacio Auxiliar:O(1)