C++ | Priority Queue| Easy Understand| Time complexity: O(nlogn)
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nWe only need to know th
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe only need to know the biggest k item of the diff between reward1 and reward2, which means, these idx choose reward1 are better.\n\n# Complexity\n- Time complexity: O(nlogn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(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        int n = reward1.size(), res = 0;\n        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;\n        for (int i = 0; i < n; i++) {\n            pq.push({reward1[i] - reward2[i], i});\n            if (pq.size() > k) {\n                pq.pop();\n            }\n        }\n        set<int> st;\n        while (!pq.empty()) {\n            auto tmp = pq.top(); pq.pop();\n            int idx = tmp.second;\n            st.insert(idx);\n            res += reward1[idx];\n        }\n        for (int i = 0; i < n; i++) {\n            if (st.count(i) == 0) {\n                res += reward2[i];\n            }\n        }\n        return res;\n    }\n};\n```
['Heap (Priority Queue)', 'C++']