Priority_Queue | C++ | Sorting
Intuition\nWe need the highest profits with unique categories, but there can also be cases where having duplicate categories give us a higher elegance value if 
# Intuition\nWe need the highest profits with unique categories, but there can also be cases where having duplicate categories give us a higher elegance value if they have big enough profit.\n\n# Approach\nSort by descending order of profits, then take first k elements and after that keep replacing the smallest profit item with the next available highest profit item which has a unique category.\nAll this time, keep taking the maximum in each iteration after k elements.\n\n\n\nU will be having only one option after picking k elements i.e\ndelete from a category with multiple insatance so we try to replace one from the remaining instances.\n\n# Complexity\n- Time complexity: O(nlogn)\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    long long findMaximumElegance(vector<vector<int>>& items, int k) \n    {\n        //GREEDY SOLUTION\n    unordered_map<int,int> mp;\n    priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>> pq;\n        sort(items.begin(),items.end(),greater<vector<int>>());\n        long long ele=0,ans=0;\n        for(int i=0;i<k;i++)\n        {\n            ele+=items[i][0];\n            mp[items[i][1]]++;\n            pq.push({items[i][0],items[i][1]});\n        }\n        ans=ele+mp.size()*mp.size();\n        int n=items.size();\n        for(int i=k;i<n && !pq.empty();i++)\n        {\n            // no need to introduce new category \n            if(mp.count(items[i][1]))\n                continue;\n            // we dont want to delete a unique category\n            auto  it=pq.top();\n            pq.pop();\n            while(!pq.empty() && mp[it.second]==1)\n            {\n                it=pq.top();\n                pq.pop();\n            }\n            if(pq.empty())\n                break;\n            // a category with multiple insatance so we try to replace one of them\n            ele+=items[i][0]-it.first;\n            mp[it.second]--;\n            mp[items[i][1]]++;\n            long long freq=mp.size()*mp.size();\n            ans=max(ans,ele+freq);\n        }\n        return ans;\n    }\n};\n```
['Greedy', 'Sorting', 'Heap (Priority Queue)', 'C++']