Clean Java Solution


  • 0
    Z

    Hi there! I am sharing my solution using single priority queue. The idea is simply greedy. Each time we choose the project with maximum profit among available ones. Thus, we need to handle two things

    • Number of available projects
    • The maximum profit among available projects

    Sorting the array by their minimal capital amount handles the first one. The second one can be handled using max heap of profits.

    public class Solution {
    
        class Project implements Comparable<Project>{
            final int capital, profit;
            public Project(int capital, int profit){
                this.capital = capital;
                this.profit = profit;
            }
            @Override
            public int compareTo(Project project){
                return Integer.compare(this.capital, project.capital);
            }
        }
        
        Project[] projects;
        
        public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
            projects = new Project[Profits.length];
            for(int i = 0 ;i<projects.length;i++) {
                projects[i] = new Project(Capital[i], Profits[i]); 
            }
            Arrays.sort(projects); // sort projects according to minimum capital needed to start 
            Queue<Integer> q = new PriorityQueue<>(Collections.reverseOrder()); // create max priority queue of profits
            q.add(0); // add dummy number to run the loop at least once
            int i = 0;
            while(k != 0 && !q.isEmpty()){
                while(i<projects.length && projects[i].capital<=W){
                    q.add(projects[i].profit);
                    i++;
                }
                W+=q.poll();
                k--;
            }
            return W;
        }
        
    }

Log in to reply
 

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