Sort+Priority Queue+Binary search||75ms Beats 99.60%
Intuition\n Describe your first thoughts on how to solve this problem. \nIPO problem is solved almost 1 year ago.\nRedo  this problem with 2 approaches.\n# Appr
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIPO problem is solved almost 1 year ago.\nRedo  this problem with 2 approaches.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n[Please turn on english subtitles if necessary]\n[https://youtu.be/W4AoobL65jA?si=yj9KWWIv3syICFW3](https://youtu.be/W4AoobL65jA?si=yj9KWWIv3syICFW3)\n1. Constuct a container `cp` with the info pair `(captial[i], profit[i])` for i=0,...,n-1\n2. Sort `cp` according to the lexicographic order( default ordering)\n3. Set a max heap (priority_queue) `pq` to hold the `profit[i]`\n4. Set `curr=0` & use a loop for i=0 to k-1 step 1 do the following:\n    - Use a loop while `curr<n and cp[curr].first<=w` push` cp[curr].second` to `pq`\n    - If pq is not empty, set `w += pq.top()`, pop the element; otherwise break the loop\n5. `w`  is the answer\n\n2nd C++ is modifying 4 as follows:\n\n6.  Set `curr=0`, `idx=0` & use a loop for i=0 to k-1 step 1 do the following:\n    -  Use binary search to find `idx` such that `capital[i]<=w` for `i<idx`, i.e. ` idx=upper_bound(cp.begin()+idx, cp.end(), make_pair(w, INT_MAX))-cp.begin()`! This takes time O(log(n-idx+1))\n    - Use a loop while `curr<idx` push` cp[curr].second` to `pq`. Same number of iterations like in 1st code, but with less time for the conditional judgement.\n    - If pq is not empty, set `w += pq.top()`, pop the element; otherwise break the loop\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nRoughly speaking at most $$O(n\\log n)$$\nBut LC said\n![ipo.png](https://assets.leetcode.com/users/images/f72b2998-70bc-4947-89e4-f5c6a566a7b2_1718413722.9540079.png)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$ \n# Code||C++ Sort+Priority Queue 89ms Beats 99.26%\n```C++ []\nclass Solution {\npublic:\n    using int2 = pair<int, int>;\n\n    static int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) \n    {\n        const int n= profits.size();\n        vector<int2> cp(n);\n\n        for (int i = 0; i < n; i++) \n            cp[i] = {capital[i], profits[i]};\n\n        sort(cp.begin(), cp.end());\n\n        priority_queue<int> pq;\n\n        int curr=0;\n        for (int i = 0; i<k; i++) {\n        //    cout<<idx<<":"<<w<<endl;\n            for ( ; curr<n && cp[curr].first<=w; curr++) \n                pq.push(cp[curr].second);\n\n            if (!pq.empty()) {\n                w += pq.top();\n                pq.pop();\n            }\n            else break;\n        }\n        return w;\n    }\n};\n\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n```Python []\nclass Solution:\n    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:\n        n=len(profits)\n        cp = list(zip(capital, profits))\n        cp.sort()\n\n        pq=[]\n        curr=0\n        for i in range(k):\n            while curr<n and cp[curr][0]<=w:\n                heapq.heappush(pq, -cp[curr][1])\n                curr+=1\n            if pq: w-=heapq.heappop(pq)\n            else: break\n        return w\n        \n```\n# Code||C++ Sort+Priority Queue+Binary search||75ms Beats 99.60%\n\nDon\'t use BS for whole array. Note that `idx=upper_bound(cp.begin()+idx, cp.end()... `\nIt may help little or may even slow down a little bit; From the numerical data, it does some help. (yes for C++; but no for python, Python slicing needs time )\nUse logical judgement `curr<n && cp[curr].first<=w` needs 2 comparisons, 1 and,  1 acces to cp[curr].first, it is O(1) times, but more time than just check `curr<idx`.\n\nMoreover,  the loop of such kind `for(int i; i<idx; i++){..}` is usually optmized by the compiler.\n```C++ []\nclass Solution {\npublic:\n    using int2 = pair<int, int>;\n\n    static int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) \n    {\n        const int n= profits.size();\n        vector<int2> cp(n);\n\n        for (int i = 0; i < n; i++) \n            cp[i] = {capital[i], profits[i]};\n\n        sort(cp.begin(), cp.end());\n\n        priority_queue<int> pq;\n\n        int curr=0, idx=0;\n        for (int i = 0; i<k; i++) {\n            // binary search find idx such that capital[i]<=w for i<idx\n            idx=upper_bound(cp.begin()+idx, cp.end(), make_pair(w, INT_MAX), less<>())-cp.begin();\n        //    cout<<idx<<":"<<w<<endl;\n            for (; curr< idx; curr++ ) \n                pq.push(cp[curr].second);\n\n            if (!pq.empty()) {\n                w += pq.top();\n                pq.pop();\n            }\n            else break;\n        }\n        return w;\n    }\n};\n\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n
['Binary Search', 'Sorting', 'Heap (Priority Queue)', 'C++', 'Python3']