Solution without Heap
IntuitionThe problem is about selecting the reward for each mouse in a way that maximizes the total reward. Each mouse has two possible rewards: reward1[i] and
# Intuition
The problem is about selecting the reward for each mouse in a way that maximizes the total reward. Each mouse has two possible rewards: `reward1[i]` and `reward2[i]`. We are given a number `k`, which specifies how many mice should get the reward from `reward1`, and the rest should get the reward from `reward2`. The task is to maximize the total reward by selecting the best possible reward for each mouse based on the given condition.

# Approach
1. **Difference Calculation**: For each mouse, we compute the difference between `reward1[i]` and `reward2[i]`. This difference helps us determine whether selecting `reward1[i]` is more beneficial compared to selecting `reward2[i]`.
  
2. **Sorting by Difference**: We sort the mice in descending order based on this difference. This allows us to prioritize mice for which selecting `reward1[i]` gives a larger advantage.

3. **Greedy Selection**: 
   - For the first `k` mice (those with the largest differences), we choose `reward1[i]` to maximize the reward.
   - For the remaining mice (those not selected for `reward1`), we select `reward2[i]`.

This greedy approach ensures that we are selecting the best reward for each mouse.

# Complexity
- **Time complexity**: Sorting the mice based on the difference takes `O(n log n)`, where `n` is the number of mice. The rest of the operations are linear, so the overall time complexity is `O(n log n)`.
  
- **Space complexity**: We use an extra vector to store the differences, so the space complexity is `O(n)`.

# Code
```cpp
class Solution {
public:
    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
        vector<pair<int, int>> ans;
        for (int i = 0; i < reward1.size(); i++) {
            ans.push_back({reward1[i] - reward2[i], i});
        }
        int totalReward = 0;
        sort(ans.rbegin(), ans.rend()); // Sort by difference in descending order
        for (int i = 0; i < reward1.size(); i++) {
            if (k > 0) {
                totalReward += reward1[ans[i].second]; // Take reward1 for k items
                k--;
            } else {
                totalReward += reward2[ans[i].second]; // Take reward2 for the rest
            }
        }
        return totalReward;
    }
};

['Greedy', 'Sorting', 'C++']