Considere una gran fiesta en la que se lleva un registro de las horas de entrada y salida de los invitados. Encuentre el tiempo en el que hay un máximo de invitados en la fiesta. Tenga en cuenta que las entradas en el registro no están en ningún orden.
Ejemplo :
Input: arrl[] = {1, 2, 9, 5, 5}
exit[] = {4, 5, 12, 9, 12}
First guest in array arrives at 1 and leaves at 4,
second guest arrives at 2 and leaves at 5, and so on.
Output: 5
There are maximum 3 guests at time 5.
A continuación se muestra un método simple para resolver este problema.
1) Recorra todos los intervalos y encuentre el tiempo mínimo y máximo (tiempo en el que llega el primer invitado y tiempo en el que se va el último invitado)
2) Cree una array de conteo de tamaño ‘max – min + 1’. Deje que la array sea count[].
3) Para cada intervalo [x, y], ejecuta un ciclo para i = x a y y haz lo siguiente en el ciclo.
cuenta[i – min]++;
4) Encuentre el índice del elemento máximo en la array de conteo. Deje que este índice sea ‘max_index’, devuelva max_index + min.
La solución anterior requiere O (max-min + 1) espacio adicional. También la complejidad del tiempo de la solución anterior depende de la duración de los intervalos. En el peor de los casos, si todos los intervalos son de ‘min’ a ‘max’, entonces la complejidad del tiempo se convierte en O((max-min+1)*n) donde n es el número de intervalos.
UnLa solución eficiente es usar el tiempo de clasificación n O (nLogn). La idea es considerar todos los eventos (todas las llegadas y salidas) en orden ordenado. Una vez que tengamos todos los eventos ordenados, podemos rastrear el número de invitados en cualquier momento y realizar un seguimiento de los invitados que han llegado, pero que no han salido.
Considere el ejemplo anterior.
arr[] = {1, 2, 10, 5, 5}
dep[] = {4, 5, 12, 9, 12}
Below are all events sorted by time. Note that in sorting, if two
events have same time, then arrival is preferred over exit.
Time Event Type Total Number of Guests Present
------------------------------------------------------------
1 Arrival 1
2 Arrival 2
4 Exit 1
5 Arrival 2
5 Arrival 3 // Max Guests
5 Exit 2
9 Exit 1
10 Arrival 2
12 Exit 1
12 Exit 0
El número total de invitados en cualquier momento se puede obtener restando
el total de salidas del total de llegadas en ese momento.
Por lo tanto, el máximo de invitados es tres en el momento 5.
A continuación se muestra la implementación del enfoque anterior. Tenga en cuenta que la implementación no crea una única lista ordenada de todos los eventos, sino que clasifica individualmente las arrays arr[] y dep[], y luego utiliza el proceso de combinación de clasificación por combinación para procesarlos juntos como una única array ordenada.
C++
// Program to find maximum guest at any time in a party
#include<iostream>
#include<algorithm>
using namespace std;
void findMaxGuests(int arrl[], int exit[], int n)
{
// Sort arrival and exit arrays
sort(arrl, arrl+n);
sort(exit, exit+n);
// guests_in indicates number of guests at a time
int guests_in = 1, max_guests = 1, time = arrl[0];
int i = 1, j = 0;
// Similar to merge in merge sort to process
// all events in sorted order
while (i < n && j < n)
{
// If next event in sorted order is arrival,
// increment count of guests
if (arrl[i] <= exit[j])
{
guests_in++;
// Update max_guests if needed
if (guests_in > max_guests)
{
max_guests = guests_in;
time = arrl[i];
}
i++; //increment index of arrival array
}
else // If event is exit, decrement count
{ // of guests.
guests_in--;
j++;
}
}
cout << "Maximum Number of Guests = " << max_guests
<< " at time " << time;
}
// Driver program to test above function
int main()
{
int arrl[] = {1, 2, 10, 5, 5};
int exit[] = {4, 5, 12, 9, 12};
int n = sizeof(arrl)/sizeof(arrl[0]);
findMaxGuests(arrl, exit, n);
return 0;
}
Java
// Java Program to find maximum guest
// at any time in a party
import java.util.*;
class GFG {
static void findMaxGuests(int arrl[], int exit[],
int n)
{
// Sort arrival and exit arrays
Arrays.sort(arrl);
Arrays.sort(exit);
// guests_in indicates number of guests at a time
int guests_in = 1, max_guests = 1, time = arrl[0];
int i = 1, j = 0;
// Similar to merge in merge sort to process
// all events in sorted order
while (i < n && j < n)
{
// If next event in sorted order is arrival,
// increment count of guests
if (arrl[i] <= exit[j])
{
guests_in++;
// Update max_guests if needed
if (guests_in > max_guests)
{
max_guests = guests_in;
time = arrl[i];
}
i++; //increment index of arrival array
}
else // If event is exit, decrement count
{ // of guests.
guests_in--;
j++;
}
}
System.out.println("Maximum Number of Guests = "+
max_guests + " at time " + time);
}
// Driver program to test above function
public static void main(String[] args)
{
int arrl[] = {1, 2, 10, 5, 5};
int exit[] = {4, 5, 12, 9, 12};
int n = arrl.length;
findMaxGuests(arrl, exit, n);
}
}
// This code is contributed by Prerna Saini
Python3
# Program to find maximum guest
# at any time in a party
def findMaxGuests(arrl, exit, n):
# Sort arrival and exit arrays
arrl.sort();
exit.sort();
# guests_in indicates number of
# guests at a time
guests_in = 1;
max_guests = 1;
time = arrl[0];
i = 1;
j = 0;
# Similar to merge in merge sort to
# process all events in sorted order
while (i < n and j < n):
# If next event in sorted order is
# arrival, increment count of guests
if (arrl[i] <= exit[j]):
guests_in = guests_in + 1;
# Update max_guests if needed
if(guests_in > max_guests):
max_guests = guests_in;
time = arrl[i];
# increment index of arrival array
i = i + 1;
else:
guests_in = guests_in - 1;
j = j + 1;
print("Maximum Number of Guests =",
max_guests, "at time", time)
# Driver Code
arrl = [1, 2, 10, 5, 5];
exit = [4, 5, 12, 9, 12];
n = len(arrl);
findMaxGuests(arrl, exit, n);
# This code is contributed
# by Shivi_Aggarwal
C#
// C# Program to find maximum guest
// at any time in a party
using System;
class GFG
{
static void findMaxGuests(int []arrl,
int []exit,
int n)
{
// Sort arrival and exit arrays
Array.Sort(arrl);
Array.Sort(exit);
// guests_in indicates number
// of guests at a time
int guests_in = 1,
max_guests = 1,
time = arrl[0];
int i = 1, j = 0;
// Similar to merge in merge sort
// to process all events in sorted order
while (i < n && j < n)
{
// If next event in sorted
// order is arrival,
// increment count of guests
if (arrl[i] <= exit[j])
{
guests_in++;
// Update max_guests if needed
if (guests_in > max_guests)
{
max_guests = guests_in;
time = arrl[i];
}
//increment index of arrival array
i++;
}
// If event is exit, decrement
// count of guests.
else
{
guests_in--;
j++;
}
}
Console.Write("Maximum Number of Guests = "+
max_guests +
" at time " + time);
}
// Driver Code
public static void Main()
{
int []arrl = {1, 2, 10, 5, 5};
int []exit = {4, 5, 12, 9, 12};
int n = arrl.Length;
findMaxGuests(arrl, exit, n);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP Program to find maximum
// guest at any time in a party
function findMaxGuests($arrl, $exit, $n)
{
// Sort arrival and exit arrays
sort($arrl);
sort($exit);
// guests_in indicates number
// of guests at a time
$guests_in = 1;
$max_guests = 1;
$time = $arrl[0];
$i = 1;
$j = 0;
// Similar to merge in merge
// sort to process all events
// in sorted order
while ($i < $n and $j < $n)
{
// If next event in sorted
// order is arrival,
// increment count of guests
if ($arrl[$i] <= $exit[$j])
{
$guests_in++;
// Update max_guests if needed
if ($guests_in > $max_guests)
{
$max_guests = $guests_in;
$time = $arrl[$i];
}
// increment index of
// arrival array
$i++;
}
// If event is exit, decrement
// count of guests.
else
{
$guests_in--;
$j++;
}
}
echo "Maximum Number of Guests = " , $max_guests
, " at time " , $time;
}
// Driver Code
$arr1 = array(1, 2, 10, 5, 5);
$exit = array(4, 5, 12, 9, 120);
$n = count($arr1);
findMaxGuests($arr1, $exit, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript Program to find maximum guest
// at any time in a party
function findMaxGuests(arrl, exit, n)
{
// Sort arrival and exit arrays
arrl.sort(function(a, b){return a - b});
exit.sort(function(a, b){return a - b});
// guests_in indicates number of guests at a time
let guests_in = 1, max_guests = 1, time = arrl[0];
let i = 1, j = 0;
// Similar to merge in merge sort to process
// all events in sorted order
while (i < n && j < n)
{
// If next event in sorted order is arrival,
// increment count of guests
if (arrl[i] <= exit[j])
{
guests_in++;
// Update max_guests if needed
if (guests_in > max_guests)
{
max_guests = guests_in;
time = arrl[i];
}
i++; //increment index of arrival array
}
else // If event is exit, decrement count
{ // of guests.
guests_in--;
j++;
}
}
document.write("Maximum Number of Guests =
" + max_guests + " at time " + time);
}
let arrl = [1, 2, 10, 5, 5];
let exit = [4, 5, 12, 9, 12];
let n = arrl.length;
findMaxGuests(arrl, exit, n);
// This code is contributed by divyeshrabadiya07.
</script>
Producción :
Maximum Number of Guests = 3 at time 5
La complejidad temporal de este método es O(nLogn).
Gracias a Gaurav Ahirwar por sugerir este método.
Otra solución eficiente:
enfoque:
1). Cree una array auxiliar utilizada para almacenar datos dinámicos de puntos de inicio y finalización.
2). Recorra toda la array de elementos y aumente el valor en el punto inicial en 1 y, de manera similar, reduzca el valor después del punto final en 1.
[Aquí usamos las expresiones “x[inicio[i]]-=1” y “x[ fin[i]+1]-=1”]
3). Durante el bucle, después de calcular la array auxiliar: agregue permanentemente el valor en el índice actual y verifique el índice de valor máximo que se desplaza de izquierda a derecha.
C++
#include<bits/stdc++.h>
using namespace std;
void maxOverlap(vector<int>& start, vector<int>& end )
{
int n= start.size();
// Finding maximum starting time O(n)
int maxa=*max_element(start.begin(), start.end());
// Finding maximum ending time O(n)
int maxb=*max_element(end.begin(), end.end());
int maxc = max(maxa, maxb);
int x[maxc + 2];
memset(x, 0, sizeof x);
int cur = 0, idx;
// Creating and auxiliary array O(n)
for(int i = 0; i < n; i++)
{
//Lazy addition
++x[start[i]];
--x[end[i]+1];
}
int maxy = INT_MIN;
//Lazily Calculating value at index i O(n)
for(int i = 0; i <= maxc; i++)
{
cur += x[i];
if(maxy < cur)
{
maxy = cur;
idx = i;
}
}
cout<<"Maximum value is "<<maxy<<" at position "<<idx<<endl;
}
// Driver code
int main()
{
vector<int> start = {13, 28, 29, 14, 40, 17, 3},
end = {107, 95, 111, 105, 70, 127, 74};
maxOverlap(start,end);
return 0;
}
Java
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
class GFG
{
public static void maxOverlap(int []start,int [] end ,int n)
{
// Finding maximum starting time
int maxa = Arrays.stream(start).max().getAsInt();
// Finding maximum ending time
int maxb = Arrays.stream(end).max().getAsInt();
int maxc = Math.max(maxa,maxb);
int []x = new int[maxc + 2];
Arrays.fill(x, 0);
int cur=0,idx=0;
// Creating an auxiliary array
for(int i = 0; i < n; i++)
{
// Lazy addition
++x[start[i]];
--x[end[i]+1];
}
int maxy=Integer.MIN_VALUE;
//Lazily Calculating value at index i
for(int i = 0; i <= maxc; i++)
{
cur+=x[i];
if(maxy < cur)
{
maxy = cur;
idx = i;
}
}
System.out.println("Maximum value is:"+
maxy+" at position: "+idx+"");
}
// Driver code
public static void main(String[] args)
{
int [] start = new int[]{13, 28, 29, 14, 40, 17, 3 };
int [] end = new int[]{107, 95, 111, 105, 70, 127, 74};
int n = start.length;
maxOverlap(start,end,n);
}
}
Python3
import sys
def maxOverlap(start,end):
n= len(start)
maxa = max(start)# Finding maximum starting time
maxb = max(end) # Finding maximum ending time
maxc=max(maxa,maxb)
x =(maxc+2)*[0]
cur=0; idx=0
for i in range(0,n) :# CREATING AN AUXILIARY ARRAY
x[start[i]]+=1 # Lazy addition
x[end[i]+1]-=1
maxy=-1
#Lazily Calculating value at index i
for i in range(0,maxc+1):
cur+=x[i]
if maxy<cur :
maxy=cur
idx=i
print("Maximum value is: {0:d}".format(maxy),
" at position: {0:d}".format(idx))
if __name__ == "__main__":
start=[13,28,29,14,40,17,3]
end=[107,95,111,105,70,127,74]
maxOverlap(start,end)
C#
// C# implementation of above approach
using System;
using System.Linq;
class GFG
{
public static void maxOverlap(int []start,int [] end ,int n)
{
// Finding maximum starting time
int maxa = start.Max();
// Finding maximum ending time
int maxb = end.Max();
int maxc = Math.Max(maxa,maxb);
int[] x = new int[maxc + 2];
int cur = 0,idx = 0;
// Creating an auxiliary array
for(int i = 0; i < n; i++)
{
// Lazy addition
++x[start[i]];
--x[end[i]+1];
}
int maxy=int.MinValue;
//Lazily Calculating value at index i
for(int i = 0; i <= maxc; i++)
{
cur+=x[i];
if(maxy < cur)
{
maxy = cur;
idx = i;
}
}
Console.WriteLine("Maximum value is "+
maxy+" at position: "+idx+"");
}
// Driver code
public static void Main()
{
int []start = {13, 28, 29, 14, 40, 17, 3 };
int []end = {107, 95, 111, 105, 70, 127, 74};
int n = start.Length;
maxOverlap(start,end,n);
}
}
// This code is contributed by chandan_jnu
PHP
<?php
function maxOverlap($start, $end )
{
$n= count($start);
// Finding maximum starting time O(n)
$maxa = max($start);
//Finding maximum ending time O(n)
$maxb = max($end);
$maxc = max($maxa, $maxb);
$x = array_fill(0, $maxc + 2, 0);
$cur = 0;
// Creating and auxiliary array O(n)
for($i = 0; $i < $n; $i++)
{
// Lazy addition
++$x[$start[$i]];
--$x[$end[$i]+1];
}
$maxy=-PHP_INT_MAX;
// Lazily Calculating value at index i O(n)
for($i = 0; $i <= $maxc; $i++)
{
$cur += $x[$i];
if($maxy < $cur)
{
$maxy = $cur;
$idx = $i;
}
}
echo "Maximum value is ".$maxy." at position ".$idx."\n";
}
// Driver code
$start = array(13,28,29,14,40,17,3);
$end = array(107,95,111,105,70,127,74);
maxOverlap($start,$end);
// This code is contributed by chandan_jnu
?>
Javascript
<script>
// Javascript implementation of above approach
function maxOverlap(start, end, n)
{
// Finding maximum starting time
let maxa = 0;
for(let i = 0; i < start.length; i++)
{
maxa = Math.max(maxa, start[i]);
}
// Finding maximum ending time
let maxb = 0;
for(let i = 0; i < end.length; i++)
{
maxb = Math.max(maxb, end[i]);
}
let maxc = Math.max(maxa,maxb);
let x = new Array(maxc + 2);
x.fill(0);
let cur = 0,idx = 0;
// Creating an auxiliary array
for(let i = 0; i < n; i++)
{
// Lazy addition
++x[start[i]];
--x[end[i]+1];
}
let maxy = Number.MIN_VALUE;
//Lazily Calculating value at index i
for(let i = 0; i <= maxc; i++)
{
cur+=x[i];
if(maxy < cur)
{
maxy = cur;
idx = i;
}
}
document.write(
"Maximum value is "+ maxy+" at position: "+idx+""
);
}
let start = [13, 28, 29, 14, 40, 17, 3 ];
let end = [107, 95, 111, 105, 70, 127, 74];
let n = start.length;
maxOverlap(start,end,n);
</script>
C++
#include<bits/stdc++.h>
using namespace std;
void maxOverlap(vector<int>& start, vector<int>& end )
{
int n= start.size();
// Finding maximum starting time O(n)
int maxa=*max_element(start.begin(), start.end());
// Finding maximum ending time O(n)
int maxb=*max_element(end.begin(), end.end());
int maxc = max(maxa, maxb);
int x[maxc + 2];
memset(x, 0, sizeof x);
int cur = 0, idx;
// Creating and auxiliary array O(n)
for(int i = 0; i < n; i++)
{
//Lazy addition
++x[start[i]];
--x[end[i]+1];
}
int maxy = INT_MIN;
//Lazily Calculating value at index i O(n)
for(int i = 0; i <= maxc; i++)
{
cur += x[i];
if(maxy < cur)
{
maxy = cur;
idx = i;
}
}
cout<<"Maximum value is "<<maxy<<" at position "<<idx<<endl;
}
// Driver code
int main()
{
vector<int> start = {13, 28, 29, 14, 40, 17, 3},
end = {107, 95, 111, 105, 70, 127, 74};
maxOverlap(start,end);
return 0;
}
Java
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
class GFG
{
public static void maxOverlap(int []start,int [] end ,int n)
{
// Finding maximum starting time
int maxa = Arrays.stream(start).max().getAsInt();
// Finding maximum ending time
int maxb = Arrays.stream(end).max().getAsInt();
int maxc = Math.max(maxa,maxb);
int []x = new int[maxc + 2];
Arrays.fill(x, 0);
int cur=0,idx=0;
// Creating an auxiliary array
for(int i = 0; i < n; i++)
{
// Lazy addition
++x[start[i]];
--x[end[i]+1];
}
int maxy=Integer.MIN_VALUE;
//Lazily Calculating value at index i
for(int i = 0; i <= maxc; i++)
{
cur+=x[i];
if(maxy < cur)
{
maxy = cur;
idx = i;
}
}
System.out.println("Maximum value is:"+
maxy+" at position: "+idx+"");
}
// Driver code
public static void main(String[] args)
{
int [] start = new int[]{13, 28, 29, 14, 40, 17, 3 };
int [] end = new int[]{107, 95, 111, 105, 70, 127, 74};
int n = start.length;
maxOverlap(start,end,n);
}
}
Python3
import sys
def maxOverlap(start,end):
n= len(start)
maxa = max(start)# Finding maximum starting time
maxb = max(end) # Finding maximum ending time
maxc=max(maxa,maxb)
x =(maxc+2)*[0]
cur=0; idx=0
for i in range(0,n) :# CREATING AN AUXILIARY ARRAY
x[start[i]]+=1 # Lazy addition
x[end[i]+1]-=1
maxy=-1
#Lazily Calculating value at index i
for i in range(0,maxc+1):
cur+=x[i]
if maxy<cur :
maxy=cur
idx=i
print("Maximum value is: {0:d}".format(maxy),
" at position: {0:d}".format(idx))
if __name__ == "__main__":
start=[13,28,29,14,40,17,3]
end=[107,95,111,105,70,127,74]
maxOverlap(start,end)
C#
// C# implementation of above approach
using System;
using System.Linq;
class GFG
{
public static void maxOverlap(int []start,int [] end ,int n)
{
// Finding maximum starting time
int maxa = start.Max();
// Finding maximum ending time
int maxb = end.Max();
int maxc = Math.Max(maxa,maxb);
int[] x = new int[maxc + 2];
int cur = 0,idx = 0;
// Creating an auxiliary array
for(int i = 0; i < n; i++)
{
// Lazy addition
++x[start[i]];
--x[end[i]+1];
}
int maxy=int.MinValue;
//Lazily Calculating value at index i
for(int i = 0; i <= maxc; i++)
{
cur+=x[i];
if(maxy < cur)
{
maxy = cur;
idx = i;
}
}
Console.WriteLine("Maximum value is "+
maxy+" at position: "+idx+"");
}
// Driver code
public static void Main()
{
int []start = {13, 28, 29, 14, 40, 17, 3 };
int []end = {107, 95, 111, 105, 70, 127, 74};
int n = start.Length;
maxOverlap(start,end,n);
}
}
// This code is contributed by chandan_jnu
PHP
<?php
function maxOverlap($start, $end )
{
$n= count($start);
// Finding maximum starting time O(n)
$maxa = max($start);
//Finding maximum ending time O(n)
$maxb = max($end);
$maxc = max($maxa, $maxb);
$x = array_fill(0, $maxc + 2, 0);
$cur = 0;
// Creating and auxiliary array O(n)
for($i = 0; $i < $n; $i++)
{
// Lazy addition
++$x[$start[$i]];
--$x[$end[$i]+1];
}
$maxy=-PHP_INT_MAX;
// Lazily Calculating value at index i O(n)
for($i = 0; $i <= $maxc; $i++)
{
$cur += $x[$i];
if($maxy < $cur)
{
$maxy = $cur;
$idx = $i;
}
}
echo "Maximum value is ".$maxy." at position ".$idx."\n";
}
// Driver code
$start = array(13,28,29,14,40,17,3);
$end = array(107,95,111,105,70,127,74);
maxOverlap($start,$end);
// This code is contributed by chandan_jnu
?>
Javascript
<script>
// Javascript implementation of above approach
function maxOverlap(start, end, n)
{
// Finding maximum starting time
let maxa = 0;
for(let i = 0; i < start.length; i++)
{
maxa = Math.max(maxa, start[i]);
}
// Finding maximum ending time
let maxb = 0;
for(let i = 0; i < end.length; i++)
{
maxb = Math.max(maxb, end[i]);
}
let maxc = Math.max(maxa,maxb);
let x = new Array(maxc + 2);
x.fill(0);
let cur = 0,idx = 0;
// Creating an auxiliary array
for(let i = 0; i < n; i++)
{
// Lazy addition
++x[start[i]];
--x[end[i]+1];
}
let maxy = Number.MIN_VALUE;
//Lazily Calculating value at index i
for(let i = 0; i <= maxc; i++)
{
cur+=x[i];
if(maxy < cur)
{
maxy = cur;
idx = i;
}
}
document.write(
"Maximum value is "+ maxy+" at position: "+idx+""
);
}
let start = [13, 28, 29, 14, 40, 17, 3 ];
let end = [107, 95, 111, 105, 70, 127, 74];
let n = start.length;
maxOverlap(start,end,n);
</script>
Producción:
Maximum value is 7 at position 40
Complejidad de tiempo : O(max(hora de salida))
Espacio auxiliar : O(max(hora de salida))
Gracias a Harshit Saini por sugerir este método.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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