Find the maximum amount that can be collected by selling movie tickets
Given an integer N and an array seats[] where N is the number of people standing in a line to buy a movie ticket and seat[i] is the number of empty seats in the ith row of the movie theater. The task is to find the maximum amount a theater owner can make by selling movie tickets to N people. Price of a ticket is equal to the maximum number of empty seats among all the rows.
Example:
Input: seats[] = {1, 2, 4}, N = 3
Output: 9
Person Empty Seats Ticket Cost 1 1 2 4 4 2 1 2 3 3 3 1 2 2 2 4 + 3 + 2 = 9
Input: seats[] = {2, 3, 5, 3}, N = 4
Output: 15
Approach: This problem can be solved by using a priority queue that will store the count of empty seats for every row and the maximum among them will be available at the top.
- Create an empty priority_queue q and traverse the seats[] array and insert all element into the priority_queue.
- Initialize two integer variable ticketSold = 0 and ans = 0 that will store the number of tickets sold and the total collection of the amount so far.
- Now check while ticketSold < N and q.top() > 0 then remove the top element from the priority_queue and update ans by adding top element of the priority queue. Also store this top value in a variable temp and insert temp – 1 back to the priority_queue.
- Repeat these steps until all the people have been sold the tickets and print the final result.
Below is the implementation of the above approach:
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> |
9
Time Complexity: O(N*logM) where N is tickets to be sold.
Explanation: In the condition of the while loop: ticketSold < N and q.top() >0, Value of N is determining the time required and here we need to maintain heap every time that needs O(Log(M))….so overall complexity will be O(N* Log(m)) where M is the size of given array.
Auxiliary Space: O(M) to store heap q.