Using Java and priority queues to solve this problem with a complexity of O(log

Question

Using Java and priority queues to solve this problem with a complexity of O(log N)

(2) Sean is a big fan of Coldplay, which is a British rock band. Coldplay is in New York City for their "A Head Full of Dreams Tour". They will perform in the MetLife Stadium. So, Sean decided to go and watch his favorite band perform. After reaching the stadium, he saw that many people have lined up for the concert tickets. He knows that there are M rows in the stadium with different seating capacities. They may or may not be equal. The price of the ticket depends on the row. If the row has K (always greater than 0) vacant seats, then the price of the ticket will be K dollars. Now, every fan standing in the line will get a ticket one by one. Given the seating capacities of different rows, find the maximum possible amount that the concert event will gain with the help of the ticket sales Input The first line consists of M and N. M denotes the number of seating rows in the stadium and N denotes the number of Coldplay fans waiting in the line to get a ticket for the match. Next line consists of M space separated integers X[1], x[2], X[3. XIM] where Xi] denotes the number of empty seats initially in the ith row Output: Print in a single line the maximum dollars the concert event will gain Constraints: 1

Explanation / Answer

The problem can't be solved in O(log N) because to get the total cost we need to sum up the costs of N fans which is O(N) and to find the max cost of each fan using the priority queue we need O(log M) operations. Thus the complexity should be O(N log M)

The corresponding java program is given bellow:

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

public class TicketSale {

   private static final int MAX_ROW=1000;
   private static final int MAX_FAN=1000;
   private static final int MAX_SEAT=1000;
  
   public static void main(String[] args) {
       /* Take inputs from keyboard with checking constraints on the value. */
       int M=0,N=0;
       int[] availableSeats=null;
       Scanner sc = new Scanner(System.in);
       boolean validInput=false;
       while(!validInput){
           validInput = true;
           System.out.println("Enter values of M and N");
           String line = sc.nextLine();
           String[] tokens = line.split("\s+");
           M=Integer.parseInt(tokens[0]);
           N=Integer.parseInt(tokens[1]);
           if(!(M>=1 && M<=MAX_ROW) || !(N>=1 && N<=MAX_FAN)){
               System.out.println("Value of M should be between 1 and "+MAX_ROW);
               System.out.println("Value of N should be between 1 and "+MAX_FAN);
               validInput = false;
               continue;
           }
           availableSeats = new int[M];
           System.out.println("Enter no. of seats for "+M+" rows");
           line = sc.nextLine();
           tokens = line.split("\s+");
           if(tokens.length<M){
               System.out.println("Enter available seat for "+M+" rows");
               continue;
           }
           int totalSeat=0;
           for(int i=0;i<M;i++){
               availableSeats[i] = Integer.parseInt(tokens[i]);
               totalSeat += availableSeats[i];
               if(availableSeats[i] > MAX_SEAT){
                   System.out.println("Max available seat per row is "+MAX_SEAT);
                   validInput = false;
                   continue;
               }
           }
           if(totalSeat <= N){
               System.out.println("Total available seat should be greater than N");
               validInput = false;
               continue;
           }
       }
       /* Create a Max Priority queue to store the available seats. */
       PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
       for(Integer i : availableSeats){
           pq.add(i);
       }
       /* Max amount at each iteration is the max availiable seat which is at the head of the Queue.
       * So delete it and add it to the totalAmount. Availiable seat of that row is decreased by 1 and
       * again insert it into the queue.
       */
       int totalAmount=0,nextValue;
       for(int i=0;i<N;i++){
           nextValue = pq.remove();
           totalAmount += nextValue;
           pq.add(nextValue-1);
       }
       /* Print the result. */
       System.out.println("Maximum possible amount = "+totalAmount);
   }
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.