Sunday, October 4, 2015

Zenefits: [OA] Sell Ticket





Code (Java):

import java.util.*;

public class Solution {
    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;
    }
} 

No comments:

Post a Comment