BASIC OBSERVATION BASED APPROACH! fully explained! 💯
Approach\nThe approach to this problem can be understood by seeing the pattern that all the cheese has to be eaten but who eats the cheese will affect the total
# Approach\nThe approach to this problem can be understood by seeing the pattern that all the cheese has to be eaten but who eats the cheese will affect the total score! \nMoreover you note that mouse1 will eat cheese first, hence it is natural that we\'d like mouse1 to eat that index of cheese which will give us a more rewarding score THAN mouse2, hence you compare both scores by using maxHeap and then mouse1 eats top k indexes cheese of that maxHeap and the rest is eaten by mouse2;\nThe time complexity will be calculated by insertions and extraction from the priority queue (max heap)!\n\nPLEASE UPVOTE IF THIS HELPED YOU!\ni\'m a beginner so please notify if u see any mistakes! i\'ll be grateful to y\'all! \n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(2n)$$ Although it can be easily brought down (i did it in a hurry lol sorry :P)\n\n# Code\n```\nclass Solution {\npublic:\n    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {\n        \n        int n = reward1.size();\n        vector<int> visited(n,0);\n\n        priority_queue< pair<int,int> > pq;\n        for(int i=0; i<n; i++){\n            pq.push({reward1[i]-reward2[i], i});\n        }\n\n        int ans=0;\n        while(k--){\n            \n            int index = pq.top().second;\n            visited[index]=1;\n            pq.pop();\n            ans += reward1[index];\n        }\n\n        for(int i=0; i<n; i++){\n            if(visited[i]==0){\n                ans += reward2[i];\n            }\n        }\n        return ans;\n    }\n};\n```
['Heap (Priority Queue)', 'C++']