Mice and Cheese - Solution & Explanation

Problem Overview: Two mice eat cheese from the same set of plates. If mouse1 eats cheese i you gain reward1[i]; if mouse2 eats it you gain reward2[i]. Exactly k cheeses must go to mouse1 and the rest to mouse2. The goal is maximizing total reward.

Approach 1: Brute Force Assignment (Exponential Time)

Try every combination of choosing k indices for mouse1 and assign the remaining cheeses to mouse2. For each combination, compute the total reward by summing reward1 for chosen indices and reward2 for the rest. This guarantees the optimal answer but requires evaluating C(n, k) possibilities, leading to O(2^n) time in the worst case and O(1) extra space. This approach mainly helps understand the decision structure: each cheese represents a binary choice.

Approach 2: Greedy with Sorting by Difference (O(n log n))

The key insight is comparing how much extra reward you gain if mouse1 eats a cheese instead of mouse2. For each index compute the difference diff = reward1[i] - reward2[i]. A large positive difference means mouse1 should strongly prefer that cheese, while a negative value means mouse2 should take it. Sort cheeses by this difference in descending order and assign the first k cheeses to mouse1. The rest automatically go to mouse2. Sorting costs O(n log n) time and the final summation is O(n), with O(n) space if you store the differences. This greedy ordering works because every assignment decision is independent once you rank the relative benefit.

Approach 3: Greedy with Heap / Priority Queue (O(n log k))

Instead of sorting the entire list, push differences (reward1[i] - reward2[i]) into a heap (priority queue). Maintain the top k largest differences using a min-heap of size k. First assume mouse2 eats every cheese and sum reward2. Then add the best k improvements from the heap to convert those plates to mouse1. Heap operations cost O(log k), producing O(n log k) time and O(k) space. This version is useful when k is much smaller than n.

The core idea is a classic greedy optimization over an array: evaluate the gain of choosing one option over another, rank those gains, and pick the best ones.

Recommended for interviews: The greedy difference strategy with sorting is the expected solution. Start by explaining the brute force choice model, then show how computing reward1[i] - reward2[i] converts the problem into selecting the top k gains. This demonstrates both correctness reasoning and practical optimization.