Dado un número entero N y una array asientos[] donde N es el número de personas que hacen fila para comprar un boleto de cine y asiento[i] es el número de asientos vacíos en la i -ésima fila del cine. La tarea es encontrar la cantidad máxima que el propietario de un cine puede ganar vendiendo boletos de cine a N personas. El precio de un boleto es igual al número máximo de asientos vacíos entre todas las filas.
Ejemplo:
Entrada: asientos[] = {1, 2, 4}, N = 3
Salida: 9
Persona Asientos vacíos Costo del boleto 1 1 2 4 4 2 1 2 3 3 3 1 2 2 2 4 + 3 + 2 = 9
Entrada: asientos[] = {2, 3, 5, 3}, N = 4
Salida: 15
Enfoque: este problema se puede resolver mediante el uso de una cola de prioridad que almacenará el recuento de asientos vacíos para cada fila y el máximo entre ellos estará disponible en la parte superior.
- Cree una cola de prioridad q vacía y recorra la array de asientos [] e inserte todos los elementos en la cola de prioridad.
- Inicialice dos variables enteras ticketSold = 0 y ans = 0 que almacenarán la cantidad de boletos vendidos y la recaudación total del monto hasta el momento.
- Ahora verifique mientras ticketSold < N y q.top() > 0 , luego elimine el elemento superior de la cola de prioridad y actualice ans agregando el elemento superior de la cola de prioridad. También almacene este valor superior en una temperatura variable e inserte temp – 1 de vuelta a la cola_prioridad.
- Repite estos pasos hasta que a todas las personas se les hayan vendido las entradas e imprime el resultado final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the maximum amount
// that can be collected by selling tickets
int maxAmount(int M, int N, int seats[])
{
// Priority queue that stores
// the count of empty seats
priority_queue<int> q;
// Insert each array element
// into the priority queue
for (int i = 0; i < M; i++) {
q.push(seats[i]);
}
// To store the total
// number of tickets sold
int ticketSold = 0;
// To store the total amount
// of collection
int ans = 0;
// While tickets sold are less than N
// and q.top > 0 then update the collected
// amount with the top of the priority
// queue
while (ticketSold < N && q.top() > 0) {
ans = ans + q.top();
int temp = q.top();
q.pop();
q.push(temp - 1);
ticketSold++;
}
return ans;
}
// Driver code
int main()
{
int seats[] = { 1, 2, 4 };
int M = sizeof(seats) / sizeof(int);
int N = 3;
cout << maxAmount(N, M, seats);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int[] seats = new int[]{ 1, 2, 4 };
// Function to return the maximum amount
// that can be collected by selling tickets
public static int maxAmount(int M, int N)
{
// Priority queue that stores
// the count of empty seats
PriorityQueue<Integer> q =
new PriorityQueue<Integer>(Collections.reverseOrder());
// Insert each array element
// into the priority queue
for (int i = 0; i < M; i++)
{
q.add(seats[i]);
}
// To store the total
// number of tickets sold
int ticketSold = 0;
// To store the total amount
// of collection
int ans = 0;
// While tickets sold are less than N
// and q.top > 0 then update the collected
// amount with the top of the priority
// queue
while (ticketSold < N && q.peek() > 0)
{
ans = ans + q.peek();
int temp = q.peek();
q.poll();
q.add(temp - 1);
ticketSold++;
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int M = seats.length;
int N = 3;
System.out.print(maxAmount(M, N));
}
}
// This code is contributed by Sanjit_Prasad
Python 3
# Python3 implementation of the approach import heapq # Function to return the maximum amount # that can be collected by selling tickets def maxAmount(M, N, seats): # Priority queue that stores # the count of empty seats q = seats # for maintaining the property of max heap heapq._heapify_max(q) # To store the total # number of tickets sold ticketSold = 0 # To store the total amount # of collection ans = 0 # While tickets sold are less than N # and q[0] > 0 then update the collected # amount with the top of the priority # queue while ticketSold < N and q[0] > 0: # updating ans # with maximum number of tickets ans += q[0] q[0] -= 1 if q[0] == 0: break # for maintaining the property of max heap heapq._heapify_max(q) ticketSold += 1 return ans # Driver Code seats = [1, 2, 4] M = len(seats) N = 3 print(maxAmount(M, N, seats)) '''Code is written by Rajat Kumar (GLAU)'''
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the maximum amount
// that can be collected by selling tickets
static int maxAmount(int M, int N, int[] seats)
{
// Priority queue that stores
// the count of empty seats
List<int> q = new List<int>();
// Insert each array element
// into the priority queue
for (int i = 0; i < M; i++) {
q.Add(seats[i]);
}
q.Sort();
q.Reverse();
// To store the total
// number of tickets sold
int ticketSold = 0;
// To store the total amount
// of collection
int ans = 0;
// While tickets sold are less than N
// and q.top > 0 then update the collected
// amount with the top of the priority
// queue
while (ticketSold < N && q[0] > 0) {
ans = ans + q[0];
int temp = q[0];
q.RemoveAt(0);
q.Add(temp - 1);
q.Sort();
q.Reverse();
ticketSold++;
}
return ans;
}
// Driver code
static void Main()
{
int[] seats = { 1, 2, 4 };
int M = seats.Length;
int N = 3;
Console.WriteLine(maxAmount(N, M, seats));
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// Javascript implementation of the approach
// Function to return the maximum amount
// that can be collected by selling tickets
function maxAmount(M, N, seats)
{
// Priority queue that stores
// the count of empty seats
let q = [];
// Insert each array element
// into the priority queue
for (let i = 0; i < M; i++) {
q.push(seats[i]);
}
q.sort(function(a, b){return a - b});
q.reverse();
// To store the total
// number of tickets sold
let ticketSold = 0;
// To store the total amount
// of collection
let ans = 0;
// While tickets sold are less than N
// and q.top > 0 then update the collected
// amount with the top of the priority
// queue
while ((ticketSold < N) && (q[0] > 0)) {
ans = ans + q[0];
let temp = q[0];
q.shift();
q.push(temp - 1);
q.sort(function(a, b){return a - b});
q.reverse();
ticketSold++;
}
return ans;
}
let seats = [ 1, 2, 4 ];
let M = seats.length;
let N = 3;
document.write(maxAmount(N, M, seats));
</script>
Producción:
9
Complejidad Temporal: O(N*logM) donde N son los boletos a vender.
Explicación : en la condición del ciclo while: ticketSold < N y q.top() >0, el valor de N determina el tiempo requerido y aquí necesitamos mantener el montón cada vez que se necesita O(Log(M))…. por lo que la complejidad general será O(N* Log(m)) donde M es el tamaño de la array dada.
Espacio auxiliar: O(M) para almacenar montón q.