O(NlogN) greedy solution.
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n1. Sort items by descen
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Sort items by descending order of profit.\n2. Add top K items. As we add items, keep the minimum profit per category where it has more than one element (since throwing away this element doesn\'t affect the #category)\n3. After K iteration, if adding a new item can increase the number of categories, then do it. Throw away the min element, and add a new one.\n\nTo keep the elements per category -> Category : minHeap (in profit)\nTo keep the min element from all minimum profits in each category -> ordered_set (ascending order in profit).\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution\n{\npublic:\n    struct Element\n    {\n        int profit;\n        int category;\n    };\n    long long findMaximumElegance(vector<vector<int>> &items, int k)\n    {\n        sort(items.begin(), items.end(), [](const vector<int> &a, const vector<int> &b)\n             { return a[0] > b[0]; });\n        long long ans = 0;\n        long long profitSum = 0;\n        unordered_map<int, priority_queue<int, vector<int>, greater<int>>> catToProfits; // min heap per cat.\n        auto elemComp = [](const Element &a, const Element &b)\n        {\n            if (a.profit < b.profit)\n                return true;\n            if (a.profit == b.profit)\n                return a.category < b.category;\n            return false;\n        };\n        set<Element, decltype(elemComp)> minProfits(elemComp);\n        int seqSize = 0;\n        for (int i = 0; i < items.size(); i++) // O(N)\n        {\n            if (seqSize < k)\n            {\n                seqSize++;\n                profitSum += items[i][0];\n                if (catToProfits[items[i][1]].size() > 0)\n                {\n                    Element curMin{catToProfits[items[i][1]].top(), items[i][1]};\n                    minProfits.erase(curMin); // if we already inserted min, than erase O(logK)\n                    catToProfits[items[i][1]].push(items[i][0]);\n                    minProfits.insert({items[i][0], items[i][1]}); // update min to new one. O(logK)\n                }\n                else\n                {\n                    catToProfits[items[i][1]].push(items[i][0]); // add O(logK)\n                }\n            }\n            else\n            {\n                // window full. Need to throw away one and add one.\n                if (minProfits.empty())\n                    break; // optimal since we have one elem per category\n                if (catToProfits.count(items[i][1]) > 0)\n                    continue; // cat already exists O(logK)\n\n                Element victim = *minProfits.begin();\n                minProfits.erase(minProfits.begin()); // erase from the set O(logK)\n                catToProfits[victim.category].pop();  // victim gets erased O(logK)\n\n                if (catToProfits[victim.category].size() >= 2)                                 // update min\n                    minProfits.insert({catToProfits[victim.category].top(), victim.category}); // O(logK)\n\n                catToProfits[items[i][1]].push(items[i][0]); // always a new one. O(logK)\n\n                profitSum -= victim.profit;\n                profitSum += items[i][0];\n            }\n\n            if (seqSize == k)\n                ans = max(ans, profitSum + (long long)catToProfits.size() * (long long)catToProfits.size());\n        }\n        return ans;\n    }\n};\n/*\n[[4,5],[4,2],[7,4],[2,3],[5,5],[5,3],[5,11],[6,4],[9,4],[1,7],[6,12],[8,10],[5,14],[8,4]]\n\n*/\n```
['C++']