We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Practice
  2. Algorithms
  3. Greedy
  4. Luck Balance
  5. Discussions

Luck Balance

  • dylanvanderberg + 0 comments

    Why not use a heap (PriorityQueue in Java) to remove the need for the O(nlog(n)) operation of sorting the array. Adding to a heap is O(log(n)) in worst-case, but O(1) in the average case. Since that happens n times, it should be faster on average. See my implementation: 

       // Complete the luckBalance function below.
    static int luckBalance(int k, int[][] contests) {
        int numLuck = 0;
        int totalImportant = 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(new Comparator<Integer>(){
            @Override
            public int compare(Integer obj1, Integer obj2){
                return obj1 - obj2;
            }
        });
        for(int[] contest : contests){
            numLuck += contest[0];
            if(contest[1] == 1){
                minHeap.offer(contest[0]);
                totalImportant++;
            }
        }
        for(int i = 0; i < totalImportant - k; i++){
            numLuck -= 2 * minHeap.poll();
        }
        return numLuck;
    }