C++ || Sorting || Binary Search on Answer
\nStep-1: We need an order that will cost maximum amount of money to complete all transactions. Then find the minimum amount using binary search.\nStep-2: How t
```\nStep-1: We need an order that will cost maximum amount of money to complete all transactions. Then find the minimum amount using binary search.\nStep-2: How to find that particular order? "Take less cashback and spend more money ".\nSplit transactions into two part:\na: cashback less than cost.\nb: cashback greater or equal to cost\n\ncase a: Sort them in ascending order of "cashback". (Take less cashback)\ncase b: Sort them in descending order of "cost". (Spend more money, because all of them are giving cashback >= cost)\n\n\n\nclass Solution {\n    static bool cmp1(vector<int> &a, vector<int> &b) {\n        if(a[1] == b[1])\n            return a[0] > b[0];\n        return a[1] < b[1];\n    }\n    \n    static bool cmp2(vector<int> &a, vector<int> &b) {\n        return a[0] > b[0];\n    }\n    \n    bool possible(vector<vector<int>>& v1, vector<vector<int>>& v2, long long ans) {\n        for(int i = 0; i < v1.size(); i++) {\n            if(ans >= v1[i][0]) \n                ans = (ans - v1[i][0] + v1[i][1]);\n            else \n                return false;\n        }\n        \n        for(int i = 0; i < v2.size(); i++) {\n            if(ans >= v2[i][0]) \n                ans = (ans - v2[i][0] + v2[i][1]);\n            else \n                return false;\n        }\n        \n        return true;\n    }\n\npublic:\n    long long minimumMoney(vector<vector<int>>& tr) {\n        vector<vector<int>> v1, v2;\n        for(int i = 0; i < tr.size(); i++) {\n            if(tr[i][1] >= tr[i][0])\n                v2.push_back({tr[i][0], tr[i][1]});\n            else \n                v1.push_back({tr[i][0], tr[i][1]});\n        }\n        \n        sort(v1.begin(), v1.end(), cmp1);\n        sort(v2.begin(), v2.end(), cmp2);\n        \n        long long ans = 0;\n        long long low = 0, high = 1e16;\n        while(low <= high) {\n            long long mid = (low + high) / 2;\n            if(possible(v1, v2, mid)) {\n                ans = mid;\n                high = mid - 1;\n            } else {\n                low = mid + 1;\n            }\n        }\n        \n        return ans;\n    }\n};\n\n```
['Binary Search', 'C', 'Sorting']