O((K + N)logN) One PriorityQueue Java Solution with Comments (60ms)


  • 0
    Z
    public class Solution {
        
        
        public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
            if (Profits == null || Capital == null) {
                return 0;
            }
            ArrayList<Pair> projects = new ArrayList<>();
            int n = Profits.length;
            for (int i = 0; i < n; i++) {
                projects.add(new Pair(Profits[i], Capital[i]));
            }
            // sort all the project with capital ascending order
            // make it convenient to check all the projects that satisfy current capital constrain
            Collections.sort(projects, new Comparator<Pair>() {
               public int compare(Pair p1, Pair p2) {
                   int diff = p1.cap - p2.cap;
                   if (diff == 0) {
                       diff = p2.prf - p1.prf;
                   }
                   return diff;
               } 
            });
            
            // maxheap : always garantee that the top of pq has maximual profit
            PriorityQueue<Pair> pq = new PriorityQueue<>(new Comparator<Pair>() {
               public int compare(Pair p1, Pair p2) {
                   int diff = p2.prf - p1.prf;
                   if (diff == 0) {
                       diff = p1.cap - p1.cap;
                   }
                   return diff;
               } 
            });
            
            // the potential project we start to look at 
            int i = 0;
            // loop for k round
            int maxCapital = W;
            for (int j = 0; j < k; j++) {
                // initialization for each round
                // put all the projects that satisfy current capital constrain into PQ
                for (; i < n; i++) {
                    if (projects.get(i).cap <= maxCapital) {
                        pq.add(projects.get(i));
                    } else {
                        break;
                    }
                }
                // the top of PQ would be our best choice of this round
                if (!pq.isEmpty()) {
                    maxCapital += pq.poll().prf;
                }
            }
            return maxCapital;
        }
    }
    
    class Pair {
        int prf;
        int cap;
        public Pair(int prf, int cap) {
            this.prf = prf;
            this.cap = cap;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.