Mice and Cheese

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.
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.

Examples

Example 1

1
2
3
4
5


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.
The total points are 4 + 4 + 3 + 4 = 15.
It can be proven that 15 is the maximum total points that the mice can achieve.

Example 2

1
2
3
4
5


Input: reward1 = [1,1], reward2 = [1,1], k = 2
Output: 2
Explanation: In this example, the first mouse eats the 0th (0-indexed) and 1st types of cheese, and the second mouse does not eat any cheese.
The total points are 1 + 1 = 2.
It can be proven that 2 is the maximum total points that the mice can achieve.

Constraints

1 <= n == reward1.length == reward2.length <= 10^5
1 <= reward1[i], reward2[i] <= 1000
0 <= k <= n

Solution

Method 1 – Greedy with Sorting by Difference

Intuition

To maximize the total points, let the first mouse eat the k cheeses where the difference reward1[i] - reward2[i] is largest, and let the second mouse eat the rest. This ensures the first mouse gets the most beneficial cheeses.

Approach

For each cheese, compute the difference reward1[i] - reward2[i].
Sort indices by this difference in descending order.
Assign the first k cheeses to the first mouse, the rest to the second mouse.
Sum the points accordingly.
Return the total maximum points.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
public:
    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
        int n = reward1.size();
        vector<pair<int, int>> diff;
        for (int i = 0; i < n; ++i) diff.push_back({reward1[i] - reward2[i], i});
        sort(diff.rbegin(), diff.rend());
        int ans = 0;
        vector<bool> chosen(n, false);
        for (int i = 0; i < k; ++i) chosen[diff[i].second] = true;
        for (int i = 0; i < n; ++i) {
            ans += chosen[i] ? reward1[i] : reward2[i];
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


func miceAndCheese(reward1, reward2 []int, k int) int {
    n := len(reward1)
    diff := make([][2]int, n)
    for i := 0; i < n; i++ {
        diff[i] = [2]int{reward1[i] - reward2[i], i}
    }
    sort.Slice(diff, func(i, j int) bool { return diff[i][0] > diff[j][0] })
    ans := 0
    chosen := make([]bool, n)
    for i := 0; i < k; i++ {
        chosen[diff[i][1]] = true
    }
    for i := 0; i < n; i++ {
        if chosen[i] {
            ans += reward1[i]
        } else {
            ans += reward2[i]
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
    public int miceAndCheese(int[] reward1, int[] reward2, int k) {
        int n = reward1.length;
        int[][] diff = new int[n][2];
        for (int i = 0; i < n; i++) diff[i] = new int[]{reward1[i] - reward2[i], i};
        Arrays.sort(diff, (a, b) -> b[0] - a[0]);
        int ans = 0;
        boolean[] chosen = new boolean[n];
        for (int i = 0; i < k; i++) chosen[diff[i][1]] = true;
        for (int i = 0; i < n; i++) ans += chosen[i] ? reward1[i] : reward2[i];
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution {
    fun miceAndCheese(reward1: IntArray, reward2: IntArray, k: Int): Int {
        val n = reward1.size
        val diff = Array(n) { i -> reward1[i] - reward2[i] to i }
        diff.sortByDescending { it.first }
        val chosen = BooleanArray(n)
        for (i in 0 until k) chosen[diff[i].second] = true
        var ans = 0
        for (i in 0 until n) ans += if (chosen[i]) reward1[i] else reward2[i]
        return ans
    }
}

1
2
3
4
5
6
7


def mice_and_cheese(reward1: list[int], reward2: list[int], k: int) -> int:
    n = len(reward1)
    diff = sorted([(reward1[i] - reward2[i], i) for i in range(n)], reverse=True)
    chosen = [False] * n
    for i in range(k):
        chosen[diff[i][1]] = True
    return sum(reward1[i] if chosen[i] else reward2[i] for i in range(n))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


impl Solution {
    pub fn mice_and_cheese(reward1: Vec<i32>, reward2: Vec<i32>, k: i32) -> i32 {
        let n = reward1.len();
        let mut diff: Vec<(i32, usize)> = (0..n).map(|i| (reward1[i] - reward2[i], i)).collect();
        diff.sort_by(|a, b| b.0.cmp(&a.0));
        let mut chosen = vec![false; n];
        for i in 0..k as usize {
            chosen[diff[i].1] = true;
        }
        (0..n).map(|i| if chosen[i] { reward1[i] } else { reward2[i] }).sum()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution {
    miceAndCheese(reward1: number[], reward2: number[], k: number): number {
        const n = reward1.length;
        const diff = Array.from({ length: n }, (_, i) => [reward1[i] - reward2[i], i]);
        diff.sort((a, b) => b[0] - a[0]);
        const chosen = Array(n).fill(false);
        for (let i = 0; i < k; ++i) chosen[diff[i][1]] = true;
        let ans = 0;
        for (let i = 0; i < n; ++i) ans += chosen[i] ? reward1[i] : reward2[i];
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n log n), for sorting the differences.
🧺 Space complexity: O(n), for storing indices and choices.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Greedy with Sorting by Difference#

Intuition#

Approach#

Code#

Complexity#