There are two mice and n different types of cheese, each type of cheese should be eaten by exactly one mouse.
A point of the cheese with index i (0-indexed) is:
reward1[i] if the first mouse eats it.reward2[i] if the second mouse eats it.You are given a positive integer array reward1, a positive integer array reward2, and a non-negative integer k.
Return the maximum points the mice can achieve if the first mouse eats exactly k types of cheese.
Example 1:
Input: reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2 Output: 15 Explanation: In this example, the first mouse eats the 2nd (0-indexed) and the 3rd types of cheese, and the second mouse eats the 0th and the 1st types of cheese. The total points are 4 + 4 + 3 + 4 = 15. It can be proven that 15 is the maximum total points that the mice can achieve.
Example 2:
Input: reward1 = [1,1], reward2 = [1,1], k = 2 Output: 2 Explanation: In this example, the first mouse eats the 0th (0-indexed) and 1st types of cheese, and the second mouse does not eat any cheese. The total points are 1 + 1 = 2. It can be proven that 2 is the maximum total points that the mice can achieve.
Constraints:
1 <= n == reward1.length == reward2.length <= 1051 <= reward1[i], reward2[i] <= 10000 <= k <= nThe key observation in #2611 Mice and Cheese is that each cheese piece gives two possible rewards depending on which mouse eats it. If all cheeses were initially assigned to the second mouse, the total reward would simply be the sum of reward2. The decision then becomes choosing k cheeses to switch to the first mouse in order to maximize the total gain.
To make this decision efficiently, compute the difference between reward1[i] and reward2[i] for each index. This difference represents the extra benefit of letting the first mouse eat that cheese. By prioritizing the cheeses with the largest positive differences, we can maximize the total reward.
This can be achieved by sorting the differences or using a max heap to pick the top k values. Sorting leads to a time complexity of O(n log n), while a heap-based approach can also efficiently select the best candidates with similar complexity.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with Sorting (sort reward differences) | O(n log n) | O(n) |
| Greedy with Max Heap / Priority Queue | O(n log k) | O(n) |
Bro Coders
Use these hints if you're stuck. Try solving on your own first.
The intended solution uses greedy approach.
Imagine at first that the second mouse eats all the cheese, then we should choose k types of cheese with the maximum sum of - reward2[i] + reward1[i].
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this type of greedy selection problem is common in coding interviews. It tests understanding of greedy strategies, sorting, and priority queues, which frequently appear in medium-level interview questions.
The optimal approach uses a greedy strategy by comparing the difference between reward1 and reward2 for each cheese. Selecting the k cheeses with the largest differences maximizes the extra reward gained by the first mouse.
A sorting approach or a priority queue (max heap) works best. Sorting the reward differences allows easy selection of the top k gains, while a heap can dynamically track the largest differences.
The difference between reward1[i] and reward2[i] represents the benefit of assigning that cheese to the first mouse instead of the second. By prioritizing the largest differences, we maximize the total reward.