JAVA | Sorting + Greedy | Explained ✅
Approach:\nThe difference of rewards will tell us which cheese to feed to which mouse. \n\nWe will do reward1[i] - reward2[i]\n\nIf difference is positive means
# Approach:\nThe difference of rewards will tell us which cheese to feed to which mouse. \n\nWe will do `reward1[i] - reward2[i]`\n\nIf difference is positive means `reward1[i]` is greater so we will feed that index\'s cheese to the first mouse.\nElse that index\'s cheese would be fed to the second mouse.\n\nSo we sort the data structure which holds the difference of rewards.\n\nThe first $$k$$ cheese would be fed to the first mouse, then the rest of the cheese after that would be fed to the second mouse.\n\n---\n\n# Solution:\n```\nclass Solution {\n    public int miceAndCheese(int[] reward1, int[] reward2, int k) {\n        int n = reward1.length;\n        int[][] r1 = new int[n][2];\n        // storing the indices along with the differences\n        // because we\'ll need to fetch the reward using the indices\n        // from the two given arrays\n        for (int i = 0; i < n; i++) {\n            r1[i] = new int[] {reward1[i] - reward2[i], i};\n        }\n        \n        // sort on the basis of difference (in descending order)\n        Arrays.sort(r1, (a, b) -> b[0] - a[0]);\n        int reward = 0;\n        \n        // feed the first top \'k\' rewarding cheese to the first mouse\n        for (int i = 0; i < k; i++) {\n            reward += reward1[r1[i][1]];\n        }\n        // feed the leftover to the second mouse\n        for (int i = k; i < n; i++) {\n            reward += reward2[r1[i][1]];\n        }\n        \n        return reward;\n    }\n}\n```\n##### Time complexity: $$O(n) + O(2n.log2n) + O(k + n - k) => O(n.logn)$$\n##### Space complexity: $$O(2.n) => O(n)$$
['Greedy', 'Sorting', 'Java']