MediumNo. 2611
Mice and Cheese — LeetCode 2611 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Greedy, Array, Sorting, Heap (Priority Queue)
- Reading time
- 2 min
- Source
- leetcode.com
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
- Time
- O(n log n)
- Space · auxiliary
- O(1) to O(n)
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
| No. | Problem | Difficulty |
|---|---|---|
| 0502 | IPO | Hard |
| 0630 | Course Schedule III | Hard |
| 0857 | Minimum Cost to Hire K Workers | Hard |
| 1353 | Maximum Number of Events That Can Be Attended | Medium |
| 1383 | Maximum Performance of a Team | Hard |
| 1686 | Stone Game VI | Medium |
Frequently asked questions
- How hard is LeetCode 2611. Mice and Cheese?
LeetCode 2611. Mice and Cheese is rated Medium on LeetCode.
- What topics does LeetCode 2611. Mice and Cheese cover?
LeetCode 2611. Mice and Cheese is tagged Greedy, Array, Sorting and Heap (Priority Queue) on LeetCode.