✅✅ Priority_Queue || Beginner Friendly Sol || C++ || Java || Python3 || C# || Javascript || C
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem asks us to maximize the total capital by selecting at most k distinct proje
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem asks us to maximize the total capital by selecting at most k distinct projects. We have a limited amount of initial capital, and each project has a minimum capital requirement and a pure profit. We need to choose the projects in such a way that we can complete at most k distinct projects, and the final maximized capital should be as high as possible.\n\nThe code uses a greedy approach to solve the problem. The basic idea is to sort the projects by the minimum capital required in ascending order. We start with the initial capital w and try to select k distinct projects from the sorted projects.(**Note : We sort the projects by their minimum capital required in ascending order because we want to consider the projects that we can afford with our current capital. By iterating over the sorted projects, we can ensure that we only consider the projects that have a minimum capital requirement less than or equal to our current capital.If we did not sort the projects, we would need to iterate over all the projects in each iteration to check if we can afford them. This would result in a time complexity of O(n^2) which is not efficient, especially if n is large.**)\nWe use a priority queue to store the profits of the available projects that we can start with the current capital. We also use a variable i to keep track of the next project that we can add to the priority queue.\n\nIn each iteration, we first add the profits of the available projects to the priority queue by iterating i until we find a project that requires more capital than our current capital. We then select the project with the highest profit from the priority queue, add its profit to our current capital, and remove it from the priority queue. If the priority queue is empty, we cannot select any more projects and break the loop.\n\nBy using a priority queue to select the project with the highest profit, we ensure that we select the most profitable project at each iteration. By iterating over the sorted projects, we ensure that we only consider the projects that we can afford with our current capital. By selecting at most k distinct projects, we ensure that we only select the most profitable projects that we can complete with our limited resources.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Create a vector of pairs `projects` to store the minimum capital required and pure profit of each project.\n2. Initialize a variable `n` to the size of the input `profits` vector.\n3. Sort the `projects` vector by the minimum capital required in ascending order.\n4. Initialize a variable `i=0`, `totalCapital = w`, `currentProjectsCount = 0` and a priority queue `maximizeCapital` to store the maximum profit we can get from a project.\n5. Loop `k` times and perform the following operations in each iteration:\n    - While `i` is less than `n` and the minimum capital required for the project at index `i` is less than or equal to the current capital `totalCapital`, push the profit of the project at index `i` to `maximizeCapital` and increment `i`.\n    - If `maximizeCapital` is empty, break out of the loop.\n    - Add the maximum profit in `maximizeCapital` to `totalCapital` and pop it out of the priority queue.\n    - Increment the currentProjectCount by 1, i.e., `currentProjectCount++`.\n6. Return the final value of `totalCapital`.\n\n# Complexity\n- Time complexity: $$O(nlogn)$$ where $$n$$ is the size of the profits vector or capital vector.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$ where $$n$$ is the size of the profits vector or capital vector.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n``` C++ []\nclass Solution {\npublic:\n    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {\n        int currentProjectsCount = 0, n = profits.size(), totalCapital = w;\n        vector<pair<int,int>> projects;\n        for(int i = 0; i < n; i++) projects.push_back(make_pair(capital[i],profits[i]));        \n        sort(projects.begin(),projects.end()); //We sort the projects by their minimum capital required in ascending order because we want to consider the projects that we can afford with our current capital. By iterating over the sorted projects, we can ensure that we only consider the projects that have a minimum capital requirement less than or equal to our current capital.\n        priority_queue<int> maximizeCapital;\n        int i = 0;\n        while(currentProjectsCount < k) {\n            //The condition projects[i].first <= totalCapital checks if the minimum capital requirement of the next project is less than or equal to our current capital totalCapital. If this condition is true, we can add the project to the priority queue because we have enough capital to start the project.\n            //We use this condition to ensure that we only add the available projects that we can afford to the priority queue. By checking the minimum capital requirement of the next project before adding it to the priority queue, we can avoid adding projects that we cannot afford, and we can focus on selecting the most profitable project that we can afford with our current capital.\n            //The loop while (i < n && projects[i].first <= totalCapital) runs until we add all the available projects that we can afford to the priority queue\n            while(i < n && projects[i].first <= totalCapital) {\n                maximizeCapital.push(projects[i].second);\n                i++;\n            }\n            // If there is not any project which can be done, then break from loop \n            if(maximizeCapital.empty()) break;\n            // else slect the maximum profit project from the heap and add it into the totalCapital Gain.\n            totalCapital += maximizeCapital.top();\n            // remove the current project from the max-heap\n            maximizeCapital.pop();\n            // current number of project is increased by 1.\n            currentProjectsCount++;\n        }\n        return totalCapital; // returning the total capital gain.\n\n    }\n};\n```\n``` Java []\nclass Solution {\n    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {\n        int currentProjectsCount = 0, n = profits.length, totalCapital = w;\n        List<int[]> projects = new ArrayList<>();\n        for (int i = 0; i < n; i++) {\n            projects.add(new int[]{capital[i], profits[i]});\n        }\n        projects.sort(Comparator.comparingInt(a -> a[0]));\n        PriorityQueue<Integer> maximizeCapital = new PriorityQueue<>(Collections.reverseOrder());\n        int i = 0;\n        while (currentProjectsCount < k) {\n            while (i < n && projects.get(i)[0] <= totalCapital) {\n                maximizeCapital.add(projects.get(i)[1]);\n                i++;\n            }\n            if (maximizeCapital.isEmpty()) break;\n            totalCapital += maximizeCapital.poll();\n            currentProjectsCount++;\n        }\n        return totalCapital;\n    }\n}\n```\n``` Python3 []\nclass Solution:\n    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n        currentProjectsCount = 0\n        n = len(profits)\n        totalCapital = w\n        projects = sorted(zip(capital, profits))\n        \n        maximizeCapital = []\n        i = 0\n        while currentProjectsCount < k:\n            while i < n and projects[i][0] <= totalCapital:\n                heapq.heappush(maximizeCapital, -projects[i][1])\n                i += 1\n            if not maximizeCapital:\n                break\n            totalCapital -= heapq.heappop(maximizeCapital)\n            currentProjectsCount += 1\n        return totalCapital\n```\n``` JavaScript []\n\n/**\n * @param {number} k\n * @param {number} w\n * @param {number[]} profits\n * @param {number[]} capital\n * @return {number}\n */\nvar findMaximizedCapital = function(k, w, profits, capital) {\n    let currentProjectsCount = 0, n = profits.length, totalCapital = w;\n    let projects = [];\n    for (let i = 0; i < n; i++) projects.push([capital[i], profits[i]]);\n    projects.sort((a, b) => a[0] - b[0]);\n    \n    let maximizeCapital = new MaxHeap();\n    let i = 0;\n    while (currentProjectsCount < k) {\n        while (i < n && projects[i][0] <= totalCapital) {\n            maximizeCapital.insert(projects[i][1]);\n            i++;\n        }\n        if (maximizeCapital.isEmpty()) break;\n        totalCapital += maximizeCapital.extractMax();\n        currentProjectsCount++;\n    }\n    return totalCapital;\n};\n\nclass MaxHeap {\n    constructor() {\n        this.heap = [];\n    }\n\n    insert(val) {\n        this.heap.push(val);\n        this._heapifyUp();\n    }\n\n    extractMax() {\n        if (this.isEmpty()) return null;\n        const max = this.heap[0];\n        const end = this.heap.pop();\n        if (!this.isEmpty()) {\n            this.heap[0] = end;\n            this._heapifyDown();\n        }\n        return max;\n    }\n\n    isEmpty() {\n        return this.heap.length === 0;\n    }\n\n    _heapifyUp() {\n        let idx = this.heap.length - 1;\n        const element = this.heap[idx];\n        while (idx > 0) {\n            const parentIdx = Math.floor((idx - 1) / 2);\n            const parent = this.heap[parentIdx];\n            if (element <= parent) break;\n            this.heap[idx] = parent;\n            idx = parentIdx;\n        }\n        this.heap[idx] = element;\n    }\n\n    _heapifyDown() {\n        let idx = 0;\n        const length = this.heap.length;\n        const element = this.heap[idx];\n        while (true) {\n            let leftChildIdx = 2 * idx + 1;\n            let rightChildIdx = 2 * idx + 2;\n            let leftChild, rightChild;\n            let swap = null;\n            if (leftChildIdx < length) {\n                leftChild = this.heap[leftChildIdx];\n                if (leftChild > element) swap = leftChildIdx;\n            }\n            if (rightChildIdx < length) {\n                rightChild = this.heap[rightChildIdx];\n                if ((swap === null && rightChild > element) || (swap !== null && rightChild > leftChild)) {\n                    swap = rightChildIdx;\n                }\n            }\n            if (swap === null) break;\n            this.heap[idx] = this.heap[swap];\n            idx = swap;\n        }\n        this.heap[idx] = element;\n    }\n}\n```\n``` C []\ntypedef struct {\n    int capital;\n    int profit;\n} Project;\n\nint cmp(const void* a, const void* b) {\n    return ((Project*)a)->capital - ((Project*)b)->capital;\n}\n\nvoid push(int* heap, int* heapSize, int val) {\n    heap[(*heapSize)++] = val;\n    int i = *heapSize - 1;\n    while (i > 0 && heap[i] > heap[(i - 1) / 2]) {\n        int temp = heap[i];\n        heap[i] = heap[(i - 1) / 2];\n        heap[(i - 1) / 2] = temp;\n        i = (i - 1) / 2;\n    }\n}\n\nint pop(int* heap, int* heapSize) {\n    int result = heap[0];\n    heap[0] = heap[--(*heapSize)];\n    int i = 0;\n    while (1) {\n        int leftChild = 2 * i + 1;\n        int rightChild = 2 * i + 2;\n        int largest = i;\n        if (leftChild < *heapSize && heap[leftChild] > heap[largest]) largest = leftChild;\n        if (rightChild < *heapSize && heap[rightChild] > heap[largest]) largest = rightChild;\n        if (largest == i) break;\n        int temp = heap[i];\n        heap[i] = heap[largest];\n        heap[largest] = temp;\n        i = largest;\n    }\n    return result;\n}\n\nint findMaximizedCapital(int k, int w, int* profits, int profitsSize, int* capital, int capitalSize) {\n    int currentProjectsCount = 0, totalCapital = w;\n    Project* projects = (Project*)malloc(profitsSize * sizeof(Project));\n    for (int i = 0; i < profitsSize; i++) {\n        projects[i].capital = capital[i];\n        projects[i].profit = profits[i];\n    }\n    qsort(projects, profitsSize, sizeof(Project), cmp);\n    \n    int* heap = (int*)malloc(profitsSize * sizeof(int));\n    int heapSize = 0;\n    int i = 0;\n    while (currentProjectsCount < k) {\n        while (i < profitsSize && projects[i].capital <= totalCapital) {\n            push(heap, &heapSize, projects[i].profit);\n            i++;\n        }\n        if (heapSize == 0) break;\n        totalCapital += pop(heap, &heapSize);\n        currentProjectsCount++;\n    }\n    free(projects);\n    free(heap);\n    return totalCapital;\n}\n```\n``` C# []\npublic class Solution {\n    public int FindMaximizedCapital(int k, int w, int[] profits, int[] capital) {\n        int currentProjectsCount = 0, n = profits.Length, totalCapital = w;\n        List<Tuple<int, int>> projects = new List<Tuple<int, int>>();\n        for (int i = 0; i < n; i++) projects.Add(new Tuple<int, int>(capital[i], profits[i]));\n        projects.Sort((a, b) => a.Item1.CompareTo(b.Item1));\n        \n        PriorityQueue<int, int> maximizeCapital = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));\n        int index = 0;\n        while (currentProjectsCount < k) {\n            while (index < n && projects[index].Item1 <= totalCapital) {\n                maximizeCapital.Enqueue(projects[index].Item2, projects[index].Item2);\n                index++;\n            }\n            if (maximizeCapital.Count == 0) break;\n            totalCapital += maximizeCapital.Dequeue();\n            currentProjectsCount++;\n        }\n        return totalCapital;\n    }\n}\n```\n![upvote.jpeg](https://assets.leetcode.com/users/images/ce196c66-2e6f-4dec-8e30-c25c2f1f7fd3_1706881698.9688694.jpeg)\n![upvote.jpeg](https://assets.leetcode.com/users/images/ce196c66-2e6f-4dec-8e30-c25c2f1f7fd3_1706881698.9688694.jpeg)\n\n\n[Instagram](https://www.instagram.com/iamsidharthaa__/)\n[LinkedIn](https://www.linkedin.com/in/sidharth-jain-36b542133)\n**If you find this solution helpful, consider giving it an upvote! Your support is appreciated. Keep coding, stay healthy, and may your programming endeavors be both rewarding and enjoyable!**
['Array', 'Greedy', 'C', 'Sorting', 'Heap (Priority Queue)', 'C++', 'Java', 'Python3', 'JavaScript', 'C#']