Mice and cheese

Array Greedy Sorting Heap (Priority Queue)

48.3% acceptance

Feb 25, 2026

675

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn mice_and_cheese(reward1: Vec<i32>, reward2: Vec<i32>, k: i32) -> i32 {
    let n = reward1.len();
    // Start by giving all to mouse 2
    let base: i32 = reward2.iter().sum();
    // Compute gain of giving cheese i to mouse 1 instead
    let mut diffs: Vec<i32> = (0..n).map(|i| reward1[i] - reward2[i]).collect();
    diffs.sort_unstable_by(|a, b| b.cmp(a)); // descending
    // Pick top k
    base + diffs[..k as usize].iter().sum::<i32>()
  }
}