✅✅✅Simple Greedy Approach, Sorting C++
Intuition\n Describe your first thoughts on how to solve this problem. \nThe constraints on this problem only allow for a O(n) or O(log n) solution. So using 01
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe constraints on this problem only allow for a O(n) or O(log n) solution. So using 01 knapsack or other dynamic programming approaches will give TLE.\n\nThis is why we need to use greedy approach.\nFor this we need to find exactly k elements with maximum benefit to the answer from reward1 array, and then remaining can be added from reward2 matrix.\n\nTo find the first k elements with maximum benefit, we need to find the difference between reward1[I] and reward2[I], and store it with their index for easier addition in later stages.\nOnce we have the differences with indices, sort the differences in descending order. This will give the best elements to be added from reward1[I] indices at the first k positions in the diff array. \nAdd the first k elements based on indices from diff, and add the remaining elements from reward2 array to form the answer.\n\n# Complexity\n- Time complexity:\nO(n * logn)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    int miceAndCheese(vector<int>& r1, vector<int>& r2, int k) {\n        vector<pair<int, int>> diff;\n        for(int i = 0; i < r1.size(); ++i)  diff.push_back({r1[i] - r2[i], i});\n        sort(diff.begin(), diff.end(),[&](auto &a, auto &b){\n            return a.first > b.first;\n        });\n        int ans = 0;\n        vector<bool> vis(r1.size(), false);\n        for(int i = 0; i < k; ++i){\n            vis[diff[i].second] = true;\n            ans += r1[diff[i].second];\n        }\n        for(int i = 0; i < r1.size(); ++i){\n            if(vis[i] == false) ans += r2[i];\n        }\n        return ans;\n    }\n};\n```\n\nPLEASE UPVOTE THE SOLUTION IF IT WAS HELPFUL
['C++']