Clean Example🔥🔥|| Full Explanation✅|| Priority Queue✅|| C++|| Java|| Python3
Intuition :\n- Here, We have to find maximum profit that can be achieved by selecting at most k projects to invest in, given an initial capital of W, a set of P
# Intuition :\n- Here, We have to find maximum profit that can be achieved by selecting at most k projects to invest in, given an initial capital of W, a set of Profits and Capital requirements for each project.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach :\n- Here we are using two priority queues, a minHeap and a maxHeap. \n- The minHeap is used to keep track of all available projects sorted by their capital requirements in ascending order. \n- The maxHeap is used to keep track of all available projects that have capital requirements less than or equal to W, sorted by their profits in descending order.\n- Then iteratively select k projects to invest in, by removing projects from the minHeap and adding them to the maxHeap as long as their capital requirements are less than or equal to W. \n- Once k projects have been selected, terminate and return the total capital available, which is equal to the initial capital plus the sum of profits of the selected projects\n<!-- Describe your approach to solving the problem. -->\n\n# Explanation to Approach :\n- See, In this Problem you have a certain amount of money and a list of projects you can invest in. Each project requires some money to start and will give you a profit. You want to invest in the projects that will give you the most profit without running out of money.\n- So we are using two Priority Queues, one for all the projects sorted by their capital requirements and another for the projects you can currently invest in sorted by their profits. \n- Then go through the capital-sorted list and add any projects to the investable list that you can currently afford. \n- Do this until you have invested in the desired number of projects or you can\'t invest in any more.\n- Then return the total amount of money you have after investing in the projects.\n\n# Explanation with an Example :\n```\nSuppose you have $W = 50 to invest, and there are five projects available\nProject\t  Capital Required\t Profit\n    P1\t        10\t          25\n    P2\t        20\t          30\n    P3\t        30\t          10\n    P4\t        40\t          50\n    P5\t        50\t          5\n\nThe goal is to choose a maximum of k projects, given a budget of W, to maximize the profit.\n\nIf k is 3, then the optimal solution is to invest in projects P1, P2, and P4, which have a total capital requirement of 70 and a total profit of 105.\n\n```\n# Calling the findMaximizedCapital method with the following arguments:\n```\nint k = 3;\nint W = 50;\nint[] Profits = {25, 30, 10, 50, 5};\nint[] Capital = {10, 20, 30, 40, 50};\n\nSolution s = new Solution();\nint result = s.findMaximizedCapital(k, W, Profits, Capital);\n\n```\n# Here is how it will work with the above values :\n- Here\'s how the solution works:\n- The code initializes two priority queues, minHeap and maxHeap, and adds all the projects to the minHeap queue, which sorts the projects by their capital requirements in ascending order.\n- The code then iterates k times and selects the projects to invest in. In each iteration, the code checks the projects in minHeap and adds the projects that you can afford to maxHeap, which sorts the projects by their profits in descending order. \n- The code continues to add projects to maxHeap until all affordable projects have been added.\n- After adding projects to maxHeap, the code checks if maxHeap is empty, which means that there are no more affordable projects to invest in. If maxHeap is empty, the code breaks the loop and returns the current amount of money you have left.\n- If maxHeap is not empty, the code selects the project with the highest profit from maxHeap, invests in it, and updates the current amount of money you have left. It then removes the selected project from maxHeap.\n- The code repeats steps 2-4 until k projects have been selected or maxHeap is empty.\n- The code returns the current amount of money you have left, which represents the maximum profit that can be achieved by selecting at most k projects.\n- In this example, the code will iterate three times, selecting projects P1, P2, and P4 to invest in. After investing in these projects, you will have 105 left, which is the maximum profit that can be achieved by selecting at most 3 projects with an initial budget of $50.\n\n# Complexity :\n- Time complexity : O(nlogn)\n- Space complexity : O(n)\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\n```\nThanks for visiting my solution.\uD83D\uDE0A\n```\n\n# Codes [C++ |Java |Python3] :\n```C++ []\nstruct T {\n  int pro;\n  int cap;\n  T(int pro, int cap) : pro(pro), cap(cap) {}\n};\n\nclass Solution {\n public:\n  int findMaximizedCapital(int k, int W, vector<int>& Profits,\n                           vector<int>& Capital) {\n    auto compareC = [](const T& a, const T& b) { return a.cap > b.cap; };\n    auto compareP = [](const T& a, const T& b) { return a.pro < b.pro; };\n    priority_queue<T, vector<T>, decltype(compareC)> minHeap(compareC);\n    priority_queue<T, vector<T>, decltype(compareP)> maxHeap(compareP);\n\n    for (int i = 0; i < Capital.size(); ++i)\n      minHeap.emplace(Profits[i], Capital[i]);\n\n    while (k--) {\n      while (!minHeap.empty() && minHeap.top().cap <= W)\n        maxHeap.push(minHeap.top()), minHeap.pop();\n      if (maxHeap.empty())\n        break;\n      W += maxHeap.top().pro, maxHeap.pop();\n    }\n\n    return W;\n  }\n};\n```\n```Java []\nclass T {\n  public int pro;\n  public int cap;\n  public T(int pro, int cap) {\n    this.pro = pro;\n    this.cap = cap;\n  }\n}\n\nclass Solution \n{\n  public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) \n  {\n    Queue<T> minHeap = new PriorityQueue<>((a, b) -> a.cap - b.cap);\n    Queue<T> maxHeap = new PriorityQueue<>((a, b) -> b.pro - a.pro);\n\n    for (int i = 0; i < Capital.length; ++i)\n      minHeap.offer(new T(Profits[i], Capital[i]));\n\n    while (k-- > 0) {\n      while (!minHeap.isEmpty() && minHeap.peek().cap <= W)\n        maxHeap.offer(minHeap.poll());\n      if (maxHeap.isEmpty())\n        break;\n      W += maxHeap.poll().pro;\n    }\n\n    return W;\n  }\n}\n```\n```Python3 []\nimport heapq\nfrom typing import List\n\nclass T:\n    def __init__(self, pro, cap):\n        self.pro = pro\n        self.cap = cap\n        \n    def __lt__(self, other):\n        return self.cap < other.cap\n\nclass Solution:\n    def findMaximizedCapital(self, k: int, W: int, Profits: List[int], Capital: List[int]) -> int:\n        minHeap = []\n        maxHeap = []\n\n        for i in range(len(Capital)):\n            heapq.heappush(minHeap, T(Profits[i], Capital[i]))\n\n        while k > 0:\n            while minHeap and minHeap[0].cap <= W:\n                t = heapq.heappop(minHeap)\n                heapq.heappush(maxHeap, (-t.pro, t.cap))\n            if not maxHeap:\n                break\n            p, c = heapq.heappop(maxHeap)\n            W -= p\n            k -= 1\n\n        return W\n```\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\n![ezgif-3-22a360561c.gif](https://assets.leetcode.com/users/images/dab789c1-ec3d-4b53-81e3-dc065466059b_1677118805.5309927.gif)\n
['Heap (Priority Queue)', 'Python', 'C++', 'Java', 'Python3']