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, c

Related Tags