✅✅ Fast 🔥🔥 Efficient 💯💯 Simplest Explanation 🏃‍♂️🏃‍♂️Dryrun🧠
Thanks for checking out my solution. Do Upvote if this helped \uD83D\uDC4D\n#### This post has been made with \u2764 by Alok Khansali\n\n\n# \uD83C\uDFAFApproac
#### Thanks for checking out my solution. Do Upvote if this helped \uD83D\uDC4D\n#### This post has been made with \u2764 by [Alok Khansali](https://leetcode.com/u/TheCodeAlpha/)\n\n\n# \uD83C\uDFAFApproach : Priority Queue\n<!-- Describe your approach to solving the problem. -->\n\n# Intuition \uD83D\uDD2E\n<!-- Describe your first thoughts on how to solve this problem. -->\n##### Sabse pehle task toh ye hain ki ghabrana nahi hai \uD83D\uDD34Hard question ko dekh ke. Iss question ki hard hone ki vajah shayad isme use hone wale data structures hain. But logic pakda ja sakta hai. \n\n##### Chalo try karte hain. Humko bola hai, ki humare paas `k` projects karne hain. College mai nahi kiye koi baat ni, question ko karwa do :)\n##### Humko di hui hai `w` capital\uD83D\uDCB0. Aur fir humein di huyi hai `capitals` ki ek table aur kaam hone ke baad ke `profits` \uD83D\uDCB8 ki ek table.\n##### Kaahani ka saar ye hai ki \uD83D\uDCDC\n> ##### Kaam karne pe milenge pese, aur kaam karwane ke liye chahiye pese.\uD83D\uDCB7\uD83D\uDCB7\uD83D\uDCB8\uD83D\uDCB8\n#### \uD83D\uDC8EKuch kaam ki baatein : Leetcode Life lessons\uD83D\uDCA1\n- Project wo hi kiya ja sakta hai jiski starting capital humari current capital se ya toh kam ho ya uske barabar ho. **Paer utne hi failaayein jitni chaadar ho**\n- Kaam poora hone par uss kaam ka profit humari current capital mai jod diya jayega. **Clear example ki kaam karke experience milega aur tum aur bade kaam le paaoge.**\n- Ab kaam aise lena hai ki profit maximum mile, **kyuki halki growth kisi ko pasand nahi aajkl.**\n- Sabse important baat, projects aap keval `k` kar sakte ho, so choose wisely. **Jeevan mai samay nirdharit hai, karm ache rakhein tatha karte rahein.**\n\n#### Iss sawal mai hum Priority Queue ka istemaal karenge. \n\n- Priority Queue ko aisa hatiyar samjho, ki jisme jab bhi kuch daalo vo ya toh ascending ya descending order mai apne aap set kardeta hai. \n- Isme kuch function ka istemaal hota hai jese C++ mai `push`, Java mai `add` and so on. \n- Aise hi nikalne ke liye bhi kuch jaadui\uD83D\uDD2E shabd hote hain jese `pop`, `poll` aadi.\n- Iske top mai humko ya toh sabse badi value mil sakti hai ya sabse choti. \n\n##### Humko chahiye ki di hui capital mai max profit wala kaam karein, iske liye hum profits ko pehle capital ke hisab se sort kardenge. Fir apni capital tak ka vo kaam dhoondenge jis se maximum profit ho. Fir ye tabtak karenge\uD83D\uDD02 Jabtak `k` projects na ho jayein, ya fir koi kaam ho hi na paaye! Baaki aur jaankari ke liye neeche algorithm padein. Aur uske baad dry run dekhein ki code chal kese raha hai.\n\n\n\n# Algorithm\uD83D\uDCDD\n### 1. Initialisation:\n   - `projectIndex` ko 0 pe set karo.\n   - `numProjects` ko `profits.size()` se set karo.\n   - Ek `projects` naam ka vector banao jo pairs ko store karega (capital required, profit).\n\n### 2. Projects ko Pair mein Convert karo:\n   - Har project ke liye, ek pair banao jisme capital required aur profit ho, aur us pair ko `projects` vector mein add karo.\n\n### 3. Projects ko Capital ke Basis pe Sort karo:\n   - Projects ko sort karo based on the capital required in ascending order.\n\n### 4. Max Heap ka Use karo:\n   - Ek max heap (`maxProfitHeap`) banao jo maximum profits ko track karega jo current capital ke andar hain.\n\n### 5. Projects Undertake karo:\n   - Har project ke liye (maximum k projects tak):\n       1. __Max Heap ko Update karo:__\n           - Jab tak `projectIndex` `numProjects` se chhota hai aur project ka capital requirement `initialCapital` se chhota ya barabar hai:\n               - Project ka profit `maxProfitHeap` mein push karo.\n               - `projectIndex` ko increment karo.\n       2. __Check karo agar Max Heap empty hai:__\n           - Agar `maxProfitHeap` empty hai, to current capital return karo.\n       3. __Max Profit Project Undertake karo:__\n           - `maxProfitHeap` se top element (maximum profit) nikal ke `initialCapital` mein add karo.\n           - `maxProfitHeap` se top element ko pop karo.\n\n### 6. Maximized Capital Return karo:\n   - `initialCapital` ko return karo jo maximum capital hai k projects undertake karne ke baad.\n___\n## Chaliye Dryrun karte hain \uD83C\uDFC3\u200D\u2642\uFE0F\n\n<details>\n<summary>DRYRUN</summary>\n\n- k = 3 (number of projects we can undertake)\n- initialCapital = 2 (initial capital available)\n- profits = [1, 2, 3, 5, 6, 7, 8, 9] (profits of each project)\n- capital = [0, 1, 2, 3, 5, 8, 13, 21] (capital required for each project)\n\n## Step-by-Step Dry Run:\n#### Step 1: Initialization\n\n    Initialize projectIndex = 0.\n    numProjects = 8 (number of projects).\n    Create a vector of pairs projects:\n\n    projects = \n    [(0, 1), (1, 2), (2, 3), (3, 5), (5, 6), (8, 7), (13, 8), (21, 9)]\n\n    Sort projects based on capital required \n    (they are already sorted in this example).\n    (In the questions its not sorted already, it will look like this only)\n\n#### Step 2: Iterating through projects\n#### Iteration 1 (currentProject = 0)\n\n    Initial capital: 2\n    Push all projects that can be started with the \n    current capital into the max heap:\n\n        Project (0, 1) \u2192 initialCapital = 2 >= 0 \u2192 Push profit 1 \u2192 maxProfitHeap = [1]\n        Project (1, 2) \u2192 initialCapital = 2 >= 1 \u2192 Push profit 2 \u2192 maxProfitHeap = [2, 1]\n        Project (2, 3) \u2192 initialCapital = 2 >= 2 \u2192 Push profit 3 \u2192 maxProfitHeap = [3, 1, 2]\n        Stop as the next project requires more capital than available.\n\n    Maximum profit project: 3\n\n        Add profit 3 to initial capital: initialCapital = 2 + 3 = 5\n        Remove the project from max heap: \n        maxProfitHeap = [2, 1]\n\n#### Iteration 2 (currentProject = 1)\n\n    Initial capital: 5\n\n    Push all projects that can be started \n    with the current capital into the max heap:\n\n        Project (3, 5) \u2192 initialCapital = 5 >= 3 \u2192 Push profit 5 \u2192 maxProfitHeap = [5, 1, 2]\n        Project (5, 6) \u2192 initialCapital = 5 >= 5 \u2192 Push profit 6 \u2192 maxProfitHeap = [6, 5, 2, 1]\n        Stop as the next project requires more capital than available.\n\n    Maximum profit project: 6\n\n        Add profit 6 to initial capital: initialCapital = 5 + 6 = 11\n        Remove the project from max heap: \n        maxProfitHeap = [5, 1, 2]\n\n#### Iteration 3 (currentProject = 2)\n\n    Initial capital: 11\n\n    Push all projects that can be started \n    with the current capital into the max heap:\n\n        Project (8, 7) \u2192 initialCapital = 11 >= 8 \u2192 Push profit 7 \u2192 maxProfitHeap = [7, 5, 2, 1]\n        Stop as the next project requires more capital than available.\n\n    Maximum profit project: 7\n\n        Add profit 7 to initial capital: initialCapital = 11 + 7 = 18\n        Remove the project from max heap: \n        maxProfitHeap = [5, 1, 2]\n\n#### Final Result:\n\n    After 3 iterations, the maximum capital available is 18.\n\n</details>\n\n____\n![image.png](https://assets.leetcode.com/users/images/4c527ace-b59e-450e-b863-46f2e2b31e15_1718435185.5886734.png)\n____\n# Code \uD83D\uDC69\u200D\uD83D\uDCBB\n```cpp []\nclass Solution\n{\npublic:\n    int findMaximizedCapital(int k, int initialCapital, vector<int> &profits, vector<int> &capital)\n    {\n        ios_base::sync_with_stdio(0);\n        int projectIndex = 0;\n        int numProjects = profits.size();\n        // Create a vector of pairs where each pair consists of (capital required, profit)\n        vector<pair<int, int>> projects;\n        for (int i = 0; i < numProjects; i++)\n            projects.push_back({capital[i], profits[i]});\n        // Sort the projects based on the capital required in ascending order\n        sort(projects.begin(), projects.end());\n        // Use a max heap to keep track of the maximum profits available within the current capital\n        priority_queue<int> maxProfitHeap;\n        // Iterate through the number of projects we can undertake\n        for (int currentProject = 0; currentProject < k; currentProject++)\n        {\n            // Push all projects that can be started with the current capital into the max heap\n            while (projectIndex < numProjects && projects[projectIndex].first <= initialCapital)\n            {\n                maxProfitHeap.push(projects[projectIndex].second);\n                projectIndex++;\n            }\n            // If no projects can be started, return the current capital\n            if (maxProfitHeap.empty())\n                return initialCapital;\n            // Add the profit of the project with the maximum profit to the current capital\n            initialCapital += maxProfitHeap.top();\n            maxProfitHeap.pop();\n        }\n        // Return the maximized capital after undertaking up to k projects\n        return initialCapital;\n    }\n};\n```\n```java []\nclass Solution {\n    public int findMaximizedCapital(int numProjects, int initialCapital, int[] profits, int[] capital) {\n        int projectIndex = 0;\n        int totalProjects = profits.length;\n\n        // Create a list of pairs where each pair consists of (capital required, profit)\n        List<int[]> projects = new ArrayList<>();\n        for (int i = 0; i < totalProjects; i++) {\n            projects.add(new int[]{capital[i], profits[i]});\n        }\n\n        // Sort the projects based on the capital required in ascending order\n        projects.sort(Comparator.comparingInt(a -> a[0]));\n\n        // Use a max heap to keep track of the maximum profits available within the current capital\n        PriorityQueue<Integer> maxProfitHeap = new PriorityQueue<>(Collections.reverseOrder());\n\n        // Iterate through the number of projects we can undertake\n        for (int currentProject = 0; currentProject < numProjects; currentProject++) {\n            // Push all projects that can be started with the current capital into the max heap\n            while (projectIndex < totalProjects && projects.get(projectIndex)[0] <= initialCapital) {\n                maxProfitHeap.add(projects.get(projectIndex)[1]);\n                projectIndex++;\n            }\n\n            // If no projects can be started, return the current capital\n            if (maxProfitHeap.isEmpty()) {\n                return initialCapital;\n            }\n\n            // Add the profit of the project with the maximum profit to the current capital\n            initialCapital += maxProfitHeap.poll();\n        }\n\n        // Return the maximized capital after undertaking up to k projects\n        return initialCapital;\n    }\n}\n```\n```python3 []\nclass Solution:\n    def findMaximizedCapital(self, numProjects: int, initialCapital: int, profits: List[int], capital: List[int]) -> int:\n        projectIndex = 0\n        totalProjects = len(profits)\n\n        # Create a list of tuples where each tuple consists of (capital required, profit)\n        projects = list(zip(capital, profits))\n\n        # Sort the projects based on the capital required in ascending order\n        projects.sort()\n\n        # Use a max heap to keep track of the maximum profits available within the current capital\n        maxProfitHeap = []\n\n        # Iterate through the number of projects we can undertake\n        for currentProject in range(numProjects):\n            # Push all projects that can be started with the current capital into the max heap\n            while projectIndex < totalProjects and projects[projectIndex][0] <= initialCapital:\n                heapq.heappush(maxProfitHeap, -projects[projectIndex][1])\n                projectIndex += 1\n\n            # If no projects can be started, return the current capital\n            if not maxProfitHeap:\n                return initialCapital\n\n            # Add the profit of the project with the maximum profit to the current capital\n            initialCapital -= heapq.heappop(maxProfitHeap)\n\n        # Return the maximized capital after undertaking up to k projects\n        return initialCapital\n\n```\n# Complexity\n\n![image.png](https://assets.leetcode.com/users/images/2c1bceac-b3e6-436b-8e37-7dd7116ca73b_1718438183.2246463.png)\n\n![image.png](https://assets.leetcode.com/users/images/d1a1e1e4-9f5b-4162-aa0c-11984a1a565e_1718438205.407444.png)\n____\n\n![upv2.jpeg](https://assets.leetcode.com/users/images/613643cb-ac31-4ac9-ab08-650267e1381b_1718438235.182807.jpeg)\n
['Greedy', 'Sorting', 'Heap (Priority Queue)', 'C++', 'Java', 'Python3']