Three lines of Python code using Heap
Intuition\nImagine all cheese are eaten by the second mouse, so the total reward is sum(reward2). Now the first mouse need to take over exactly k cheese, and fo
# Intuition\nImagine all cheese are eaten by the second mouse, so the total reward is `sum(reward2)`. Now the first mouse need to take over exactly `k` cheese, and for each time a cheese `i` is taken by the first mouse, we earn an extra reward equals to `reward1[i] - reward2[i]`. To maximize the total reward, we want to take the top `k` reward diffs.\n\n# Approach\nUse heap to get the top K diffs, and these are the all extra rewards comparing to the reward2 case, so we can simply do the summation\n```\nmax_sum = sum(reward2) + sum(top_k_diff)\n```\n\n# Complexity\n- Time complexity:\n$$O(nlog(k))$$ \n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution:\n    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n        top_k_diff = heapq.nlargest(k, [reward1[i] - reward2[i] for i in range(len(reward1))])\n\n        max_sum = sum(reward2) + sum(top_k_diff)\n        return max_sum\n\n\n```
['Python3']