Mice and Cheese — LeetCode 2611 Python Solution

The problem

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.

Example

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.

Python solution

class Solution:
    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:
        n = len(reward1)
        idx = sorted(range(n), key=lambda i: reward1[i] - reward2[i], reverse=True)
        return sum(reward1[i] for i in idx[:k]) + sum(reward2[i] for i in idx[k:])

Complexity

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2611. Mice and Cheese is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Related problems