Greedy solution in java with proof using exchange argument
IntuitionOn a high level, this problems expects us to maximize a cost function, let's say TotalReward wherein, the problem expects us to pick exactly k rewrads
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
On a high level, this problems expects us to maximize a cost function, let's say TotalReward wherein, the problem expects us to pick exactly ```k``` rewrads from the first array (and the remaining ones from second).

Since, a cost function needs to be maximized, the first idea which comes to our mind is greedy, which indeed works here. This solution borrows the major idea from [Tim Roughgarden's lectures on Exchange Argument](https://www.youtube.com/watch?v=NTFmxA3qgoo&list=PLEAYkSg4uSQ37A6_NrUnTHEKp6EkAxTMa&index=78), a very helpful method to proof optimality of any greedy choice. Basically we define a greedy criteria to pick candidates (as per greedy criteria) and use exhange argument to demonstrate that any other candidate will result in lowering the cost function. We'll use the same idea here.

# Approach
<!-- Describe your approach to solving the problem. -->
Let's choose two greedy criterias here to demonstrate the idea and will see only of them will lead to optimal solution. The greedy criterias are as follows:

For simplicity, let's assume that k = 1.

1. Pick a value (index i) from ```reward1``` having maximum value.
2. Pick a value (index i) from ```reward1```, such that its ```reward1[i] - reward2[i]``` is maximum.

Now, let's use exchange argument to see which one leads to optimal solution. 

For #1, can I pick another ```index i` ```, which increases my cost function. Yes, let's see below example.

Example. 
reward1 = [14, 44]
reward2 = [ 0, 37]

As per our greedy criteria, we pick 44 which results in TotalReward = (44 + 0), since k = 1, will pick 0 from index i = 0. Now, clearly this is not an optimal solution since we can pick 14 and 37. This essentially means that we are able to find the exchange for our greedy candidate, hence this is not an optimal solution.

Let's try the same with greedy criteria #2, here will pick 14 and 37. This gives us optimal solution and there is no better candidate. We will prove the same as follows:

```
Let's assume first we take all type 2 cheese, say totalReward = X 
Now, let's assume k = 1, which type 1 cheese should we pick.

Claim:- Pick the one (ith index) which highest reward1[i] - reward2[i] 
        that maximizes totalReward, i.e. X + reward1[i] - reward2[i]
 
Proof:- By exchange argument, let's say we pick another i` (which results in a better solution) and hence, totalReward` = X + reward1[i`] - reward2[i`].

Since, totalReward` > totalReward, that also means, reward1[i'] - reward2[i'] > reward1[i] - reward2[i], which contradicts our greedy criteria, hence this criteria is optimal. 
```

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$$O(n)$$

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(n)$$

# Code
```java []
class Solution {
    public int miceAndCheese(int[] reward1, int[] reward2, int k) {
        int N = reward1.length;
        int totalReward = 0;
        for (int reward: reward2) {
            totalReward += reward;
        }

        PriorityQueue<Integer> pQueue = new PriorityQueue<>((i, j) -> -((reward1[i] - reward2[i]) - (reward1[j] - reward2[j])));
        for (int i = 0 ; i < N ; i++) {
            pQueue.add(i);
        }

        for (int i = 0 ; i < k ; i++) {
            int idx = pQueue.poll();
            totalReward += reward1[idx];
            totalReward -= reward2[idx];
        }

        return totalReward;
    }

    // Let's assume first we take all type 2 cheese, say totalReward = X 
    // Now, let's assume k = 1, which type 1 cheese should we pick.
    // Claim:- Pick the one (ith index) which highest reward1[i] - reward2[i] 
    //         that maximizes totalReward, i.e. X + reward1[i] - reward2[i]
    // 
    // Proof:- By exchange argument, let's say we pick another i`, then 
    // totalReward` = X + reward1[i'] - reward2[i'].
    //
    // Since, reward1[i'] - reward2[i'] < reward1[i] - reward2[i], hence 
    // totalReward` < totalReward for any i`
}
```
['Greedy', 'Heap (Priority Queue)', 'Java']