LC Hard made Easy | Well Explained⭐💯
Problem Description\nYou are given k projects, each with a capital requirement and a profit. You have an initial capital w. Your goal is to find the maximum cap
## Problem Description\nYou are given `k` projects, each with a capital requirement and a profit. You have an initial capital `w`. Your goal is to find the maximum capital you can achieve after completing at most `k` projects. You can only start a project if you have the required capital.\n\n## Detailed Approach\n\n### Intuition\nTo maximize the capital after completing up to `k` projects, we should always choose the most profitable project that we can afford with the current capital.\n\n### Steps\n1. **Pairing and Sorting**:\n   - Create pairs of (capital, profit) for each project.\n   - Sort these pairs based on the capital required in ascending order.\n\n2. **Using a Max-Heap**:\n   - Use a max-heap (priority queue) to keep track of the most profitable projects that can be undertaken with the available capital.\n\n3. **Iterate through Projects**:\n   - Initialize an index `i` to track the position in the sorted list.\n   - Iterate `k` times:\n     - Add all projects that can be started with the current capital to the max-heap.\n     - If the max-heap is not empty, extract the project with the maximum profit and add its profit to the current capital.\n     - If the max-heap is empty, break the loop as no more projects can be started.\n\n4. **Return the Result**:\n   - After completing up to `k` projects, return the final capital.\n\n### Complexity Analysis\n- **Time Complexity**: \n  - Sorting the projects takes \\(O(n \\log n)\\).\n  - Each insertion/deletion in the heap takes \\(O(\\log n)\\).\n  - In the worst case, there can be up to `k` insertions and deletions for each of the `n` projects.\n  - Thus, the overall time complexity is \\(O(n \\log n + k \\log n)\\).\n- **Space Complexity**: \\(O(n)\\) due to storage required for the sorted list and the priority queue.\n\n### Dry Run\nConsider the following example:\n- `k = 2`\n- `w = 0`\n- `profits = [1, 2, 3]`\n- `capital = [0, 1, 1]`\n\n**Step-by-Step Execution**:\n\n1. **Pairing and Sorting**:\n   - Projects: `[(0, 1), (1, 2), (1, 3)]`\n   - Sorted Projects: `[(0, 1), (1, 2), (1, 3)]`\n\n2. **Initialization**:\n   - `i = 0`\n   - Max-Heap: `[]`\n   - Current Capital: `w = 0`\n\n3. **First Iteration (`k = 2`)**:\n   - Add projects with capital requirement `<= w` to the heap:\n     - Add project `(0, 1)` to heap \u2192 Max-Heap: `[1]`\n     - `i` increments to `1`\n   - Extract max profit from heap and add to `w`:\n     - Max profit: `1` \u2192 New capital `w = 1`\n     - Heap after extraction: `[]`\n   - Remaining iterations: `k = 1`\n\n4. **Second Iteration (`k = 1`)**:\n   - Add projects with capital requirement `<= w` to the heap:\n     - Add project `(1, 2)` to heap \u2192 Max-Heap: `[2]`\n     - Add project `(1, 3)` to heap \u2192 Max-Heap: `[3, 2]`\n     - `i` increments to `3`\n   - Extract max profit from heap and add to `w`:\n     - Max profit: `3` \u2192 New capital `w = 4`\n     - Heap after extraction: `[2]`\n   - Remaining iterations: `k = 0`\n\n5. **Final Result**:\n   - After completing up to `k` projects, the final capital is `4`.\n\n### Code Implementation\n```cpp\nclass Solution {\npublic:\n    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {\n        \n        int n = profits.size(); \n        vector<pair<int,int>> projects;\n\n        for(int i = 0; i < n; i++) {\n            projects.push_back({capital[i], profits[i]});\n        }\n\n        sort(projects.begin(), projects.end());\n        int i = 0; \n        priority_queue<int> maxHeap;\n\n        while(k--) {\n            while(i < n && projects[i].first <= w) {\n                maxHeap.push(projects[i].second);\n                i++;\n            }\n\n            if(maxHeap.empty()) {\n                break;\n            }\n\n            w += maxHeap.top();\n            maxHeap.pop();\n        }\n\n        return w;\n    }\n};\n
['Array', 'Greedy', 'Sorting', 'Heap (Priority Queue)', 'C++']