Easy JAVA solution | O(n log n) in best case | Greedy Approach
\n\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nUsing greedy algorithm to solve the problem. The algorithm can be described as 
![image.png](https://assets.leetcode.com/users/images/fe8cf117-2e88-4a25-a5c6-435327962a64_1677121252.2894087.png)\n\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUsing greedy algorithm to solve the problem. The algorithm can be described as follows:\n\n- Find the maximum capital required among all projects.\n- If the initial capital (W) is greater than or equal to the maximum capital, then simply add the top k profitable projects to the initial capital using a max heap.\n- If the initial capital is less than the maximum capital, then iterate over k iterations, and at each iteration, choose the most profitable project whose capital requirement is less than or equal to the current capital (W). Add the profit of this project to W and mark this project as completed by setting its capital requirement to Integer.MAX_VALUE.\n\n# Complexity\n- Time complexity:\n**Worst Case: O(nk)**\n**Best Case: O(n log n)**\n\n- Space complexity:\nThe space complexity of the given code is **$$`O(n)`$$**, where **n is the number of projects**. The space is used to store the Profits and Capital arrays, which have a size of n. Additionally, the code uses a priority queue (max heap) to store the top k profitable projects, which can have a maximum size of k. Therefore, the overall space complexity is O(n + k). However, since k is a constant input parameter and it is guaranteed to be smaller than n, we can **simplify the space complexity to O(n)**.\n\n# I know you haven\'t SO\n![image.png](https://assets.leetcode.com/users/images/fe8cf117-2e88-4a25-a5c6-435327962a64_1677121252.2894087.png)\n\n\n# Code\n```\nclass Solution {\n    public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {\n        int maxCapital = 0;\n        for(int i = 0 ; i < Capital.length; i++){\n            maxCapital = Math.max(Capital[i], maxCapital);\n        }\n        \n        if(W >= maxCapital){\n            PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>(){\n                @Override\n                public int compare(Integer a , Integer b){\n                    return a-b;\n                }\n            });\n            for (int p: Profits) {\n                maxHeap.add(p);\n                if (maxHeap.size() > k) maxHeap.poll();    \n            }\n            for (int h: maxHeap) W += h; \n            return W;\n        }\n        \n        int index;\n        int n = Profits.length;\n        for(int i = 0; i < Math.min(k, n); i++) {\n            index = -1; \n            for(int j = 0; j < n; ++j) { \n                if (W >= Capital[j] && (index == -1 || Profits[index] < Profits[j])){\n                        index = j;\n                }\n            }\n            if(index == -1) break;\n            W += Profits[index];\n            Capital[index] = Integer.MAX_VALUE;                \n        }\n        return  W;     \n    }\n}\n```
['Java']