Zenefits: MJ [7] Sell Ticket

LIKE CODING: MJ [7] Sell Ticket

Objec­tive: Given ‘N’ win­dows where each win­dow con­tains cer­tain num­ber of tick­ets at each win­dow. Price of a ticket is equal to num­ber of tick­ets remain­ing at that win­dow. Write an algo­rithm to sell ‘k’ tick­ets from these win­dows in such a man­ner so that it gen­er­ates the max­i­mum revenue.

http://algorithms.tutorialhorizon.com/generate-maximum-revenue-by-selling-k-tickets-from-n-windows/

  PriorityQueue<Integer> pq;

  // we will create a max heap

  public MaxRevenueTickets(int length) {

    pq = new PriorityQueue<>(length, new Comparator<Integer>() {

      @Override

      public int compare(Integer o1, Integer o2) {

        // TODO Auto-generated method stub

        return o2 - o1;

      }

    });

  }

  public int calculate(int[] windowsTickets, int tickets) {

    int revenue = 0;

    // insert the all the elements of an array into the priority queue

    for (int i = 0; i < windowsTickets.length; i++) {

      pq.offer(windowsTickets[i]);

    }

    while (tickets > 0) {

      int ticketPrice = pq.poll();

      revenue += ticketPrice;

      pq.offer(--ticketPrice);

      tickets--;

    }

    return revenue;

  }

    int sellTicket(int n, int m, vector<int> a){

        int rev = 0;

        priority_queue<int> q;

        for(auto i:a) q.push(i);

        while(m){

            int r = q.top();

            q.pop();

            rev += r--;

            q.push(r);

            m--;

        }

        cout<<"rev is "<<rev<<endl;

        return rev;

    }

    int sellTicket_opt(int n, int m, vector<int> a){

        int rev = 0;

        a.push_back(0);

        sort(a.begin(), a.end(), std::greater<int>());

        int h = a[0], i = 1;

        while(i<=n && m>0){

            if(h==a[i]&&i<=n){i++;}

            int d = h-a[i];

            if(m>=d*i){

                    rev += i*(a[i]+1+h)*d/2;

            }else{

                    int d1 = m/i, d2 = m%i;

                    rev += i*(2*h-d1+1)*d1/2+(h-d1)*d2;

            }

            m = max(0, m-d*i);

            h = a[i++];

        }

        cout<<"rev is "<<rev<<endl;

        return rev;

    }

};

    a = {2,5};

    sol.sellTicket_opt(2, 4, a);

    cout<<"the answer is 14\n";

http://buttercola.blogspot.com/2015/10/zenefits-oa-word-rank.html

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

         

        int numWindows = 0;

        int numTickets = 0;

         

        numWindows = scanner.nextInt();

        numTickets = scanner.nextInt();

         

        int[] prices = new int[numWindows];

        for (int i = 0; i < numWindows; i++) {

            prices[i] = scanner.nextInt();

        }

         

        int result = maximumRevenue(prices, numTickets);

         

        System.out.println(result);

         

        scanner.close();

    }

     

    public static int maximumRevenue(int[] A, int m) {

        if (A == null || A.length == 0) {

            return 0;

        }

         

        int max = 0; //the max revenue earned

        Arrays.sort(A);

        int left = A.length - 1;

        int tickets = 0;

        while (tickets < m) {

            if ((A.length - left) + tickets > m) {

                max += (m - tickets) * A[left];

                tickets = m;

            } else {

                tickets += A.length - left;

                max += (A.length - left) * A[left];

                A[left]--;

            }

            if ((left - 1 >= 0 && A[left] == A[left - 1]) ) {

                left--;

            }

        }

        return max;

    }

Read full article from LIKE CODING: MJ [7] Sell Ticket