Simple heap | Top K maximum elements
Intuition\nTo find which elements of the reward1 list should be taken, we can take out the top K maximum elements of reward1 list.\nAnd then carry on as require
# Intuition\nTo find which elements of the reward1 list should be taken, we can take out the top K maximum elements of reward1 list.\nAnd then carry on as required.\n\nBut every time when we choose an index of reward1 we are discarding the corresponding reward for mice2. And since we need to maximize the collective result.\nIt might be possible that when we are choosing some ith maximum element of the reward1 X, and there was some element at ith position of reward2 Y, \nsuch that\n Y >>> X\nin such cases we are not maximizing the result.\n\nSo, how to handle this?\nSimple find the difference between r1[i] and r2[i] and take indexes of top K maximum elements from there.  \n\n\n\n# Complexity\n- Time complexity:\nO(n log k)\n\n- Space complexity:\nO(k)\n\nIf you didn\'t understand how the space and time complexity comes out to be this, try to solve questions related to top K frequent elements\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    \n    unordered_set<int> getIndex(vector<int>& reward1, int k) {\n        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> minHeap;\n        for (int i=0; i<reward1.size(); i++) {\n            int num = reward1[i];\n            minHeap.push({num, i});\n            if (minHeap.size() > k) {\n                minHeap.pop();\n            }\n        }\n        unordered_set<int> idx;\n        while (!minHeap.empty()) {\n            idx.insert(minHeap.top().second);\n            minHeap.pop();\n        }\n        return idx;\n    }\n    \n    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {\n        int n = reward1.size(), ans = 0;\n        vector<int> diff(n,0);\n        for(int i=0; i<n; i++)\n        {\n            diff[i] = reward1[i] - reward2[i];\n        }\n        unordered_set<int> index = getIndex(diff, k);\n        for(int i=0; i<n; i++)\n        {\n            if(index.count(i))\n            {\n                ans += reward1[i];\n            }else ans += reward2[i];\n        }\n        if(k>=n)\n        {\n            ans = accumulate(reward1.begin(), reward1.end(), 0);\n            return ans;\n        }\n        return ans;\n    }\n};\n```\n```Java []\npublic class Solution {\n    public Set<Integer> getIndex(List<Integer> reward1, int k) {\n        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(Map.Entry.comparingByKey());\n        for (int i = 0; i < reward1.size(); i++) {\n            int num = reward1.get(i);\n            minHeap.offer(new AbstractMap.SimpleEntry<>(num, i));\n            if (minHeap.size() > k) {\n                minHeap.poll();\n            }\n        }\n        Set<Integer> idx = new HashSet<>();\n        while (!minHeap.isEmpty()) {\n            idx.add(minHeap.poll().getValue());\n        }\n        return idx;\n    }\n\n    public int miceAndCheese(List<Integer> reward1, List<Integer> reward2, int k) {\n        int n = reward1.size(), ans = 0;\n        List<Integer> diff = new ArrayList<>(n);\n        for (int i = 0; i < n; i++) {\n            diff.add(reward1.get(i) - reward2.get(i));\n        }\n        Set<Integer> index = getIndex(diff, k);\n        for (int i = 0; i < n; i++) {\n            if (index.contains(i)) {\n                ans += reward1.get(i);\n            } else {\n                ans += reward2.get(i);\n            }\n        }\n        if (k >= n) {\n            ans = reward1.stream().mapToInt(Integer::intValue).sum();\n            return ans;\n        }\n        return ans;\n    }\n}\n```\n```Python3 []\nclass Solution:\n    def getIndex(self, reward1: List[int], k: int) -> set:\n        minHeap = []\n        for i, num in enumerate(reward1):\n            heapq.heappush(minHeap, (num, i))\n            if len(minHeap) > k:\n                heapq.heappop(minHeap)\n        idx = set()\n        while minHeap:\n            idx.add(heapq.heappop(minHeap)[1])\n        return idx\n    \n    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n        n = len(reward1)\n        ans = 0\n        diff = [reward1[i] - reward2[i] for i in range(n)]\n        index = self.getIndex(diff, k)\n        for i in range(n):\n            if i in index:\n                ans += reward1[i]\n            else:\n                ans += reward2[i]\n        if k >= n:\n            ans = sum(reward1)\n            return ans\n        return ans\n```
['Heap (Priority Queue)', 'C++', 'Java', 'Python3']