Maximiza el beneficio después de vender las entradas

Dada la array asientos[] donde asiento[i] es el número de asientos vacantes en la i ^-ésima fila en un estadio para un partido de cricket. Hay N personas en una cola esperando para comprar los boletos. Cada asiento cuesta igual al número de asientos libres en la fila a la que pertenece. La tarea es maximizar la ganancia vendiendo las entradas a N personas.

Ejemplos: 

Entrada: asientos[] = {2, 1, 1}, N = 3 
Salida: 4 
Persona 1: Vender el asiento en la fila con 
2 asientos libres, asientos = {1, 1, 1} 
Persona 2: Todas las filas tienen 1 
asiento vacante cada uno, asientos[] = {0, 1, 1} 
Persona 3: asientos[] = {0, 0, 1}

Entrada: asientos[] = {2, 3, 4, 5, 1}, N = 6 
Salida: 22 
 

Enfoque: para maximizar la ganancia, el boleto debe ser para el asiento en una fila que tiene el número máximo de asientos vacantes y el número de asientos vacantes en esa fila se reducirá en 1 ya que uno de los asientos se acaba de vender. . A todas las personas se les puede vender un billete de asiento hasta que queden plazas libres. Esto se puede calcular de manera eficiente con la ayuda de una cola de prioridad .

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximized profit
int maxProfit(int seats[], int k, int n)
{
 
    // Push all the vacant seats
    // in a priority queue
    priority_queue<int> pq;
    for (int i = 0; i < k; i++)
        pq.push(seats[i]);
 
    // To store the maximized profit
    int profit = 0;
 
    // To count the people that
    // have been sold a ticket
    int c = 0;
    while (c < n) {
 
        // Get the maximum number of
        // vacant seats for any row
        int top = pq.top();
 
        // Remove it from the queue
        pq.pop();
 
        // If there are no vacant seats
        if (top == 0)
            break;
 
        // Update the profit
        profit = profit + top;
 
        // Push the updated status of the
        // vacant seats in the current row
        pq.push(top - 1);
 
        // Update the count of persons
        c++;
    }
    return profit;
}
 
// Driver code
int main()
{
    int seats[] = { 2, 3, 4, 5, 1 };
    int k = sizeof(seats) / sizeof(int);
    int n = 6;
 
    cout << maxProfit(seats, k, n);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG {
 
// Function to return the maximized profit
static int maxProfit(int seats[], int k, int n)
{
     
    // Push all the vacant seats
    // in a priority queue
    PriorityQueue<Integer> pq;
    pq = new PriorityQueue<>(Collections.reverseOrder());
     
    for(int i = 0; i < k; i++)
       pq.add(seats[i]);
 
    // To store the maximized profit
    int profit = 0;
 
    // To count the people that
    // have been sold a ticket
    int c = 0;
    while (c < n)
    {
 
        // Get the maximum number of
        // vacant seats for any row
        int top = pq.remove();
 
        // If there are no vacant seats
        if (top == 0)
            break;
 
        // Update the profit
        profit = profit + top;
 
        // Push the updated status of the
        // vacant seats in the current row
        pq.add(top - 1);
 
        // Update the count of persons
        c++;
    }
     
    return profit;
}
     
// Driver Code
public static void main(String args[])
{
    int seats[] = { 2, 3, 4, 5, 1 };
    int k = seats.length;
    int n = 6;
 
    System.out.println(maxProfit(seats, k ,n));
}
}
 
// This code is contributed by rutvik_56

# Python3 implementation of the approach
import heapq
# Function to return the maximized profit
 
 
def maxProfit(seats, k, n):
    # Push all the vacant seats
    # in a max heap
    pq = seats
    # for maintaining the property of max heap
    heapq._heapify_max(pq)
    # To store the maximized profit
    profit = 0
    while n > 0:
        # updating the profit value
        # with maximum number of vacant seats
        profit += pq[0]
        pq[0] -= 1
        # If there are no vacant seats
        if pq[0] == 0:
            break
        # for maintaining the property of max heap
        heapq._heapify_max(pq)
        # decrementing the ticket count
        n -= 1
 
    return profit
 
 
# Driver Code
seats = [2, 3, 4, 5, 1]
k = len(seats)
n = 6
print(maxProfit(seats, k, n))
 
'''Code is written by Rajat Kumar (GLAU)'''

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to return the maximized profit
static int maxProfit(int[] seats, int k, int n)
{
     
    // Push all the vacant seats
    // in a priority queue
    List<int> pq = new List<int>();
    for(int i = 0; i < k; i++)
        pq.Add(seats[i]);
   
    // To store the maximized profit
    int profit = 0;
   
    // To count the people that
    // have been sold a ticket
    int c = 0;
     
    while (c < n)
    {
         
        // Get the maximum number of
        // vacant seats for any row
        pq.Sort();
        pq.Reverse();
        int top = pq[0];
   
        // Remove it from the queue
        pq.RemoveAt(0);
   
        // If there are no vacant seats
        if (top == 0)
            break;
   
        // Update the profit
        profit = profit + top;
   
        // Push the updated status of the
        // vacant seats in the current row
        pq.Add(top - 1);
   
        // Update the count of persons
        c++;
    }
    return profit;
}
 
// Driver Code
static void Main()
{
    int[] seats = { 2, 3, 4, 5, 1 };
    int k = seats.Length;
    int n = 6;
     
    Console.Write(maxProfit(seats, k, n));
}
}
 
// This code is contributed by divyeshrabadiya07

<script>
    // Javascript implementation of the approach
     
    // Function to return the maximized profit
    function maxProfit(seats, k, n)
    {
 
        // Push all the vacant seats
        // in a priority queue
        let priorityQueue = counter.map((item) => item);
 
        // To store the maximized profit
        let profit = 0;
 
        while (n != 0)
        {
 
            // Get the maximum number of
            // vacant seats for any row
            priorityQueue.sort((a,b) => b - a);
            let top = priorityQueue[0];
 
            // Remove it from the queue
            priorityQueue.shift();
 
            // If there are no vacant seats
            if (top == 0)
                break;
 
            // Update the profit
            profit = profit + top;
 
            // Push the updated status of the
            // vacant seats in the current row
            priorityQueue.push(top - 1);
 
            // Update the count of persons
            n--;
        }
        return profit;
    }
     
    let seats = [ 2, 3, 4, 5, 1 ];
    let k = seats.length;
    let n = 6;
      
    document.write(maxProfit(seats, k, n));
 
</script>

22

Complejidad del tiempo: O(n*log(n))

Espacio Auxiliar: O(n) 

Enfoque de ventana deslizante:

El problema también se puede resolver utilizando la técnica de la ventana deslizante.

• Para cada persona necesitamos vender el boleto que tiene el precio máximo y disminuir su valor en 1.
• Ordenar los asientos de la array.
• Mantenga dos punteros apuntando al máximo actual y al siguiente número máximo de asientos.
• Iteramos hasta que nuestro n>0 y hay un segundo elemento más grande en la array.
• En cada iteración, si asientos[i] > asientos[j], agregamos el valor en asientos[i],min(n, ij) veces a nuestra respuesta y decrementamos el valor en el i-ésimo índice; de ​​lo contrario, encontramos j tal que asientos[j ]<asientos[i]. Si no hay tal j, rompemos.
• Si al final de la iteración nuestro n>0 y asientos[i]!=0 agregamos asientos[i] hasta n>0 y asientos[i]!=0.

#include <bits/stdc++.h>
using namespace std;
int maxProfit(int seats[],int k, int n)
{
    sort(seats,seats+k);
    int ans = 0;
    int i = k - 1;
    int j = k - 2;
    while (n > 0 && j >= 0) {
        if (seats[i] > seats[j]) {
            ans = ans + min(n, (i - j)) * seats[i];
            n = n - (i - j);
            seats[i]--;
        }
        else {
            while (j >= 0 && seats[j] == seats[i])
                j--;
            if (j < 0)
                break;
            ans = ans + min(n, (i - j)) * seats[i];
            n = n - (i - j);
            seats[i]--;
        }
    }
    while (n > 0 && seats[i] != 0) {
        ans = ans + min(n, k) * seats[i];
        n -= k;
        seats[i]--;
    }
    return ans;
}
int main()
{
    int seats[] = { 2, 3, 4, 5, 1 };
    int k = sizeof(seats) / sizeof(int);
    int n = 6;
 
    cout << maxProfit(seats, k, n);
 
    return 0;
}

// Java program for the above approach
 
import java.util.Arrays;
 
class GFG {
 
    static int maxProfit(int seats[], int k, int n)
    {
        Arrays.sort(seats, 0, k);
        int ans = 0;
        int i = k - 1;
        int j = k - 2;
        while (n > 0 && j >= 0) {
            if (seats[i] > seats[j]) {
                ans = ans + Math.min(n, (i - j)) * seats[i];
                n = n - (i - j);
                seats[i]--;
            }
            else {
 
                while (j >= 0 && seats[j] == seats[i])
                    j--;
 
                if (j < 0)
                    break;
 
                ans = ans + Math.min(n, (i - j)) * seats[i];
                n = n - (i - j);
                seats[i]--;
            }
        }
        while (n > 0 && seats[i] != 0) {
            ans = ans + Math.min(n, k) * seats[i];
            n -= k;
            seats[i]--;
        }
        return ans;
    }
 
    public static void main(String[] args)
    {
        int seats[] = { 2, 3, 4, 5, 1 };
        int k = seats.length;
        int n = 6;
 
        System.out.println(maxProfit(seats, k, n));
    }
}
 
// This code is contributed by rajsanghavi9.

# Python3 program for the above approach
def maxProfit(seats,k, n):
 
    seats.sort()
     
    ans = 0
    i = k - 1
    j = k - 2
    while (n > 0 and j >= 0):
        if (seats[i] > seats[j]):
            ans = ans + min(n, (i - j)) * seats[i]
            n = n - (i - j)
            seats[i] -= 1
         
        else:
            while (j >= 0 and seats[j] == seats[i]):
                j -= 1
            if (j < 0):
                break
            ans = ans + min(n, (i - j)) * seats[i]
            n = n - (i - j)
            seats[i] -= 1
         
     
    while (n > 0 and seats[i] != 0):
        ans = ans + min(n, k) * seats[i]
        n -= k
        seats[i] -= 1
     
    return ans
 
seats = [2, 3, 4, 5, 1]
k = len(seats)
n = 6
print(maxProfit(seats, k, n))
 
# This code is contributed by shinjanpatra

// C# program for the above approach
 
using System;
 
class GFG {
 
    static int maxProfit(int []seats, int k, int n)
    {
        Array.Sort(seats, 0, k);
        int ans = 0;
        int i = k - 1;
        int j = k - 2;
        while (n > 0 && j >= 0) {
            if (seats[i] > seats[j]) {
                ans = ans + Math.Min(n, (i - j)) * seats[i];
                n = n - (i - j);
                seats[i]--;
            }
            else {
 
                while (j >= 0 && seats[j] == seats[i])
                    j--;
 
                if (j < 0)
                    break;
 
                ans = ans + Math.Min(n, (i - j)) * seats[i];
                n = n - (i - j);
                seats[i]--;
            }
        }
        while (n > 0 && seats[i] != 0) {
            ans = ans + Math.Min(n, k) * seats[i];
            n -= k;
            seats[i]--;
        }
        return ans;
    }
 
    public static void Main(String[] args)
    {
        int []seats = { 2, 3, 4, 5, 1 };
        int k = seats.Length;
        int n = 6;
 
        Console.Write(maxProfit(seats, k, n));
    }
}
 
// This code is contributed by shivanisinghss2110

<script>
 
function maxProfit(seats,k, n)
{
    seats.sort();
     
    var ans = 0;
    var i = k - 1;
    var j = k - 2;
    while (n > 0 && j >= 0) {
        if (seats[i] > seats[j]) {
            ans = ans + Math.min(n, (i - j)) * seats[i];
            n = n - (i - j);
            seats[i]--;
        }
        else {
            while (j >= 0 && seats[j] == seats[i])
                j--;
            if (j < 0)
                break;
            ans = ans + Math.min(n, (i - j)) * seats[i];
            n = n - (i - j);
            seats[i]--;
        }
    }
    while (n > 0 && seats[i] != 0) {
        ans = ans + Math.min(n, k) * seats[i];
        n -= k;
        seats[i]--;
    }
    return ans;
}
 
var seats = [2, 3, 4, 5, 1];
var k = seats.length;
var n = 6;
document.write(maxProfit(seats, k, n));
 
// This code is contributed by rrrtnx.
</script>

22

Complejidad de tiempo: O(k logk), donde k es el tamaño de la array dada de asientos
Espacio auxiliar: O(1)