✅ C++ || Easy To Understand || Using Multimap ✅
Intuition\n Describe your first thoughts on how to solve this problem. \nwe need to take k maximum rewards in reward1 arr and remaining index from reward2 arr t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nwe need to take k maximum rewards in reward1 arr and remaining index from reward2 arr to maximize the rewards of mice.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can use multimap to store the difference (reward2-reward1) at every index so that multimap sorts them and we can add the values of first k indexes of reward1 in map. Remaining all indexes will be of reward2. The need to store diff is because of this kind of testcases:\nreward1 = [3,3]\nreward2 = [3,5]\nk=1;\nhere if you dont use diff then you will return 6 but answer is 8.\n\n# Complexity\n- Time complexity: Nlog(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: N\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {\n        multimap<int,int> m;\n        int ans = 0;\n        for(int i=0;i<reward1.size();i++){\n            m.insert({reward2[i]-reward1[i],i});\n        }\n        int bt = 0;\n        multimap<int, int>::iterator itr;\n        for (itr = m.begin(); itr != m.end() ; ++itr) {\n            if(bt<k){\n                ans+=reward1[itr->second];\n                bt++;\n            }else{\n                ans+=reward2[itr->second];\n            }\n    }\n        return ans;\n        \n    }\n};\n```
['Ordered Map', 'C++']