Sort-greedy-two pointer solution
Intuition\n Describe your first thoughts on how to solve this problem. \nFirst idea was to use a DP approach in O(n^2). Fortunately, by checking the constraints
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFirst idea was to use a DP approach in $$O(n^2)$$. Fortunately, by checking the constraints I hinted at the fact that this might not work and a greedy approach might be more interesting.\nIt is clear that if a number is maximal and its category is not in the solution then we must select it. The issue arises when a number left in our list is maximal but its category has already been selected.\n\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nI iterate over my max_heap and if the element I\'m checking is of a new category I add it to solution, otherwise I save it on a second list (maximal_only).\n\nIf I have selected fewer elements than k, I add the highest values in our maximal list.\n\n\nNext we iterate over our solution and max array and see how many elements we should remove from our solution.\nThis step is a two pointer approach, we will remove from the end of the solution and add from the front of our maximal_values.\n\nAt each step \'removing\' (check code) I compute the gain of removing the smallest value in our solution and adding the highest value in our maximal_values array.\nSuch gain can be computed as:\n$$max\\_num - (min\\_num + 2\\cdot(variety-removing-1) + 1)$$\nTo keep track changes in variety affecting our solution we use this simple equality:\n$$n^2 - (n-1)^2 = n^2 - n^2 - 2n - 1 = -2n - 1$$\n\nWe save which removing index gives the maximal gain and compute the solution as\n```\nsum(solution) + variety^2 + max_gain + sum(maximal_only[:i])\n```\nwhere taken is our set of different values in the solution and i = k - len(taken).\n# Complexity\n- Time complexity:\n$$O(n \\log n)$$ The cost of sorting.\n- Space complexity:\n$$ O(n) $$ The cost of saving our n values.\n\n# Code\n```python []\nclass Solution(object):\n    def findMaximumElegance(self, items, k):\n        """\n        :type items: List[List[int]]\n        :type k: int\n        :rtype: int\n        """\n        profits = {}\n        taken = set()\n        max_values = []\n\n        for profit, category in items:\n            if category not in profits:\n                profits[category] = [-profit]\n            else:\n                heapq.heappush(profits[category], -profit)\n            heapq.heappush(max_values, (-profit, category))\n        \n        solution = []\n        maximal_only = []\n        res = 0\n        t = k\n        while max_values and t > 0:\n            prof, cat = max_values[0]\n            prof = - prof\n            if cat not in taken:\n                t -= 1\n                taken.add(cat)\n                solution.append(prof)\n            else:\n                maximal_only.append(prof)\n            heapq.heappop(max_values)\n\n        i = k - len(taken)\n        variety = len(taken)\n        removing = 0\n        gain = 0\n        max_rem, max_gain = 0, 0\n        n = len(solution)\n\n        while i+removing < len(maximal_only):\n            gain +=  maximal_only[i+removing] - (2*(variety-removing-1) + 1 + solution[n-removing-1])\n            removing += 1\n            if gain > max_gain:\n                max_gain = gain\n                max_rem = removing\n            t -= 1\n                \n        return sum(solution) + variety**2 + max_gain + sum(maximal_only[:i])\n\n\n\n```
['Python']