• + 1 comment

    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;
        }