✅ Reward1 - Reward2 Sorting Desc✔️ || Easy Intuitive || Explained🔥
Approach\nThis is a Greedy approach. From 2 array I want all values from reward2 but also want to replace k values from reward1 which are greater than reward2 (
### Approach\nThis is a Greedy approach. From 2 array I want all values from reward2 but also want to replace k values from reward1 which are greater than reward2 (the larger difference will be prioritize first) so that maximum sum can be achieved.\n\n### Example 1\nLet\'s take an example:\n[1,9,3,4]\n[4,4,1,1]\n2\n\nReward2 sum = 10\nso, diff vector will be : -3, 5, 2, 3\nafter, desc sorting : 5, 3, 2, -3\nthis represent what if we take reward1 value istead of reward2.\nSo, just added this to the sum. So, 10 + 5 = 15; 15 + 3 = 18 (Ans)\n\n### Example 2\n1, 1, 1, 1\n4, 4, 2, 3\nk = 2\nso, reward 2 total sum is : 13\n-> diff array: -3, -3, -1, -2\n-> desc sort : -1, -2, -3, -3\n-> after k num adding: 13 + (-1) = 12; 12 + (-2) = 10 (Ans)\n\n### Solution 1 (Easy Vector Sort)\n**c++**\n```\nint miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {\n    vector<int> v;\n    long long sum = 0;\n    for (int i = 0; i < reward1.size(); i++) {\n        v.push_back(reward1[i] - reward2[i]);\n        sum += reward2[i];\n    }\n\n    sort(v.begin(), v.end(), greater<int>());\n\n    for (int i = 0; i < k; i++)\n        sum += v[i];\n\n    return sum;\n}\n```\n\n### Solution 2 (Priority Queue)\nPriority Queue can be used for optimization.\nRef: https://leetcode.com/problems/kth-largest-element-in-an-array/\n```\nint miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {\n    priority_queue<int, vector<int>, greater<int>> pq;\n    long long sum = 0;\n    for (int i = 0; i < reward1.size(); i++) {\n        pq.push(reward1[i] - reward2[i]);\n        sum += reward2[i];\n        if (pq.size() > k)\n            pq.pop();\n    }\n\n    while (!pq.empty())\n    {\n        sum += pq.top();\n        pq.pop();\n    }\n\n    return sum;\n}\n```\n
['Greedy', 'C', 'Sorting']