El gerente de un hotel tiene que procesar N reservas anticipadas de habitaciones para la próxima temporada. Su hotel tiene habitaciones K. Las reservas contienen una fecha de llegada y una fecha de salida. Quiere saber si hay suficientes habitaciones en el hotel para satisfacer la demanda.
La idea es ordenar las arrays y realizar un seguimiento de las superposiciones.
Ejemplos:
Input : Arrivals : [1 3 5]
Departures : [2 6 8]
K: 1
Output: False
Hotel manager needs at least two
rooms as the second and third
intervals overlap.
Enfoque 1
La idea es almacenar las horas de llegada y salida en una array auxiliar con un marcador adicional para indicar si la hora es de llegada o de salida. Ahora ordena la array. Procese la array ordenada, para cada incremento de llegada de reservas activas. Y por cada salida, decremento. Realice un seguimiento de las reservas activas máximas. Si el recuento de reservas activas en cualquier momento es superior a k, devuelve falso. De lo contrario, devuelve verdadero.
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;
bool areBookingsPossible(int arrival[],
int departure[], int n, int k)
{
vector<pair<int, int> > ans;
// create a common vector both arrivals
// and departures.
for (int i = 0; i < n; i++) {
ans.push_back(make_pair(arrival[i], 1));
ans.push_back(make_pair(departure[i], 0));
}
// sort the vector
sort(ans.begin(), ans.end());
int curr_active = 0, max_active = 0;
for (int i = 0; i < ans.size(); i++) {
// if new arrival, increment current
// guests count and update max active
// guests so far
if (ans[i].second == 1) {
curr_active++;
max_active = max(max_active,
curr_active);
}
// if a guest departs, decrement
// current guests count.
else
curr_active--;
}
// if max active guests at any instant
// were more than the available rooms,
// return false. Else return true.
return (k >= max_active);
}
int main()
{
int arrival[] = { 1, 3, 5 };
int departure[] = { 2, 6, 8 };
int n = sizeof(arrival) / sizeof(arrival[0]);
cout << (areBookingsPossible(arrival,
departure, n, 1)
? "Yes\n"
: "No\n");
return 0;
}
Java
// Java implementation of the above approach
import java.io.*;
import java.util.*;
// User defined Pair class
class Pair {
int x;
int y;
// Constructor
public Pair(int x, int y)
{
this.x = x;
this.y = y;
}
}
// class to define user defined conparator
class Compare {
static void compare(Pair arr[], int n)
{
// Comparator to sort the pair according to second element
Arrays.sort(arr, new Comparator<Pair>() {
@Override public int compare(Pair p1, Pair p2)
{
return p1.x - p2.x;
}
});
}
}
class GFG
{
static boolean areBookingsPossible(int arrival[],
int departure[],
int n, int k)
{
Pair ans[] = new Pair[2*n];
// create a common vector both arrivals
// and departures.
int j = 0;
for (int i = 0; i < n; i++)
{
ans[i + j] = new Pair(arrival[i], 1);
ans[i + j + 1] = new Pair(departure[i], 0);
j++;
}
// sort the vector
Compare obj = new Compare();
obj.compare(ans, 2 * n);
int curr_active = 0, max_active = 0;
for (int i = 0; i < 2 * n; i++)
{
// if new arrival, increment current
// guests count and update max active
// guests so far
if (ans[i].y == 1)
{
curr_active++;
max_active = Math.max(max_active,
curr_active);
}
// if a guest departs, decrement
// current guests count.
else
curr_active--;
}
// if max active guests at any instant
// were more than the available rooms,
// return false. Else return true.
return (k >= max_active);
}
// Driver code
public static void main(String[] args)
{
int arrival[] = { 1, 3, 5 };
int departure[] = { 2, 6, 8 };
int n = arrival.length;
System.out.println(areBookingsPossible(arrival, departure, n, 1) ? "Yes" : "No");
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 code for the above approach.
def areBookingsPossible(arrival, departure, n, k):
ans = []
# Create a common vector both arrivals
# and departures.
for i in range(0, n):
ans.append((arrival[i], 1))
ans.append((departure[i], 0))
# Sort the vector
ans.sort()
curr_active, max_active = 0, 0
for i in range(0, len(ans)):
# If new arrival, increment current
# guests count and update max active
# guests so far
if ans[i][1] == 1:
curr_active += 1
max_active = max(max_active,
curr_active)
# if a guest departs, decrement
# current guests count.
else:
curr_active -= 1
# If max active guests at any instant
# were more than the available rooms,
# return false. Else return true.
return k >= max_active
# Driver Code
if __name__ == "__main__":
arrival = [1, 3, 5]
departure = [2, 6, 8]
n = len(arrival)
if areBookingsPossible(arrival,
departure, n, 1):
print("Yes")
else:
print("No")
# This code is contributed by Rituraj Jain
Javascript
<script>
// JavaScript implementation of the above approach
function areBookingsPossible(arrival, departure, n, k)
{
var ans = [];
// create a common vector both arrivals
// and departures.
for (var i = 0; i < n; i++) {
ans.push([arrival[i], 1]);
ans.push([departure[i], 0]);
}
// sort the vector
ans.sort();
var curr_active = 0, max_active = 0;
for (var i = 0; i < ans.length; i++) {
// if new arrival, increment current
// guests count and update max active
// guests so far
if (ans[i][1] == 1) {
curr_active++;
max_active = Math.max(max_active,
curr_active);
}
// if a guest departs, decrement
// current guests count.
else
curr_active--;
}
// if max active guests at any instant
// were more than the available rooms,
// return false. Else return true.
return (k >= max_active);
}
var arrival = [1, 3, 5];
var departure = [2, 6, 8];
var n = arrival.length;
document.write(areBookingsPossible(arrival,
departure, n, 1)
? "Yes"
: "No");
</script>
No
Complejidad de Tiempo: O(n Log n)
Espacio Auxiliar: O(n)
Enfoque 2
La idea es simplemente ordenar las 2 arrays (Array para fechas de llegada y Array para fechas de salida) primero.
Ahora, el siguiente paso sería verificar cuántas superposiciones hay en un rango en particular. Si el número de superposiciones es mayor que el número de habitaciones, podemos decir que tenemos menos habitaciones para alojar huéspedes.
Por lo tanto, para un rango particular donde la fecha de llegada (la iésima de la array de llegada) es la fecha de inicio y la fecha de salida (la iésima de la array de salida) es la fecha de finalización, la superposición solo puede ser posible si las próximas fechas de llegada (desde i+1) son menor que la fecha de finalización del rango y mayor o igual que la fecha de inicio del rango (Dado que se trata de una array ordenada, no es necesario que nos preocupemos por la última condición).
Teniendo en cuenta el hecho de que hemos ordenado la array, debemos verificar directamente si la próxima fecha de llegada Kth (i + Kth) cae en el rango, si es así, todas las fechas anteriores a esa fecha de llegada también caerán en el rango tomado, resultando en superposiciones de K+1 con el rango en cuestión, por lo tanto, excediendo el número de habitaciones.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
string areBookingsPossible(int A[], int B[],
int K, int N)
{
sort(A, A + N);
sort(B, B + N);
for(int i = 0; i < N; i++)
{
if (i + K < N && A[i + K] < B[i])
{
return "No";
}
}
return "Yes";
}
// Driver Code
int main()
{
int arrival[] = { 1, 2, 3 };
int departure[] = { 2, 3, 4 };
int N = sizeof(arrival) / sizeof(arrival[0]);
int K = 1;
cout << (areBookingsPossible(
arrival, departure, K, N));
return 0;
}
// This code is contributed by rag2127
Java
// Java code implementation of the above approach
import java.util.*;
class GFG
{
static String areBookingsPossible(int []A, int []B,
int K)
{
Arrays.sort(A);
Arrays.sort(B);
for(int i = 0; i < A.length; i++)
{
if (i + K < A.length && A[i + K] < B[i])
{
return "No";
}
}
return "Yes";
}
// Driver Code
public static void main(String []s)
{
int []arrival = { 1, 2, 3 };
int []departure = { 2, 3, 4 };
int K = 1;
System.out.print(areBookingsPossible(
arrival, departure, K));
}
}
// This code is contributed by Pratham76
Python
# Python Code Implementation of the above approach def areBookingsPossible(A, B, K): A.sort() B.sort() for i in range(len(A)): if i+K < len(A) and A[i+K] < B[i] : return "No" return "Yes" if __name__ == "__main__": arrival = [1, 2, 3] departure = [2, 3, 4] K = 1 print areBookingsPossible(arrival,departure,K) # This code was contributed by Vidhi Modi
C#
// C# code implementation of the above approach
using System;
class GFG{
static string areBookingsPossible(int []A, int []B,
int K)
{
Array.Sort(A);
Array.Sort(B);
for(int i = 0; i < A.Length; i++)
{
if (i + K < A.Length && A[i + K] < B[i])
{
return "No";
}
}
return "Yes";
}
// Driver Code
static void Main()
{
int []arrival = { 1, 2, 3 };
int []departure = { 2, 3, 4 };
int K = 1;
Console.Write(areBookingsPossible(
arrival, departure, K));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript code implementation of
// the above approach
function areBookingsPossible(A, B, K, N)
{
A.sort();
B.sort();
for(let i = 0; i < N; i++)
{
if (i + K < N && A[i + K] < B[i])
{
return "No";
}
}
return "Yes";
}
// Driver code
let arrival = [ 1, 2, 3 ];
let departure = [ 2, 3, 4 ];
let N = arrival.length;
let K = 1;
document.write(areBookingsPossible(
arrival, departure, K, N));
// This code is contributed by suresh07
</script>
Yes
Complejidad de tiempo: O(n Log n)
Espacio auxiliar: O(n) utilizado por Python sort
Enfoque 3
La idea es agregar las horas de llegada y salida de cada reserva a una lista y luego agregarla a otra lista de listas. Después de eso, ordenaremos la lista según el orden creciente de los tiempos de llegada. En caso de que dos reservas tengan la misma hora de llegada, lo ordenaremos en función de las horas de salida anticipadas.
Cree una cola de prioridad (min-heap) y recorra cada reserva de la array ordenada. Para cada recorrido, presione la hora de salida en la cola de prioridad y disminuya el valor de k (número de habitaciones). Si el valor de k llega a cero, significa que no tenemos habitaciones disponibles, entonces extraeremos la hora mínima de salida de la habitación con la ayuda de nuestra cola de prioridad.
Podemos aceptar la reserva solo y solo si esa hora mínima de salida es inferior a la hora de llegada de la reserva o si es imposible aceptar la reserva.
A continuación se muestra la implementación del enfoque anterior:
Java
/*package whatever //do not write package name here */
import java.util.*;
class GFG {
public static boolean areBookingsPossible(int arrival[], int departure[], int n, int k) {
List<List<Integer>> list = new ArrayList<>();
for(int i = 0; i < arrival.length; i++) {
List<Integer> li = new ArrayList<>();
li.add(arrival[i]);
li.add(departure[i]);
list.add(li);
}
//sorting the List
Collections.sort(list, new Comp());
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int i = 0; i < list.size(); i++) {
if(list.get(i).get(0) != list.get(i).get(1)) {
if(k > 0) {
k--;
pq.add(list.get(i).get(1));
} else {
if(pq.peek() <= list.get(i).get(0)) {
pq.remove();
pq.add(list.get(i).get(1));
} else {
return false;
}
}
}
}
return true;
}
// Driver code
public static void main(String[] args)
{
int arrival[] = { 1, 3, 5 };
int departure[] = { 2, 6, 8 };
int n = arrival.length;
System.out.println(areBookingsPossible(arrival, departure, n, 1) ? "Yes" : "No");
}
}
class Comp implements Comparator<List<Integer>> {
public int compare (List<Integer> l1, List<Integer> l2) {
if(l1.get(0) < l2.get(0)) {
return -1;
} else if(l1.get(0) == l2.get(0)) {
if(l1.get(1) < l2.get(1)) {
return -1;
} else {
return 1;
}
} else {
return 1;
}
}
}
//This code is contributed by darshanagrawalla06
Complejidad de tiempo : O (n Log n)
Espacio Auxiliar : O(k)
Publicación traducida automáticamente
Artículo escrito por Aashish Chauhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA