Greedy
Intuition\nAs is often typical with subsequence problems, we may first think of a dynammic programming approach. However, having the state be something like the
# Intuition\nAs is often typical with subsequence problems, we may first think of a dynammic programming approach. However, having the state be something like the current item and the number of distinct values accumulated so far is too large.\n\nWhen there are strict bounds for a dynamic programming approach, a common theme is to optimize that approach using a greedy algorithm.\n\n# Approach\nTo find a greedy algorithm, it is common to make some observations first.\n\nFirst, if we ignore the categories, it is clearly best to choose the `k` items with the highest profit.\n\nSecond, since it seems optimal to choose larger profits, we loop through the items in order of decreasing profit. While looping, let\'s say that we are considering whether or not to swap one of the top `k` items with some other item `item`. We have two cases.\n\na. `item` shares a category with one of the items we already have.\n\nIn this case, it is not optimal to swap the items, since we would have the same categories but decrease our profit if we swapped the items.\n\nb. `item` does not share a category with one of the items we already have.\n\nFirst, note that if we have already `l` distinct categories, then we have already found the optimal solution for `l` distinct categories since any other configuration would result in a lower profit for at least one of the items, meaning a lower profit overall. As such, we should try to swap `item` with some item in our current collection.\n\nSpecifically, we will swap `item` with the lowest profit item that is in a category that already has at least one other item. This ensures the number of distinct categories increases to `l + 1`.\n\nWe can find the lowest profit item using a priority queue.\n\n# Complexity\n- Time complexity: $$O(n\\lg n)$$\n\n- Space complexity: $$O(n)$$\n\n# Code\n```python\nclass Solution:\n    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:\n        items.sort(key=lambda item: item[0], reverse=True)\n        \n        grouped = defaultdict(list)\n        for profit, category in items[:k]:\n            grouped[category].append(profit)\n        \n        duplicates = []\n        for category, group in grouped.items():\n            group.sort(reverse=True)\n            if len(group) > 1:\n                duplicates.extend(grouped[category][1:])\n        heapify(duplicates)\n            \n        curSum = sum(profit for profit, category in items[:k])\n        res = curSum + len(grouped) ** 2\n        \n        for profit, category in items[k:]:\n            if category in grouped:\n                continue\n            \n            if not duplicates:\n                break\n            \n            duplicate = heappop(duplicates)\n            curSum -= duplicate\n            curSum += profit\n            grouped[category].append(profit)\n            \n            res = max(curSum + len(grouped) ** 2, res)\n        \n        return res\n```
['Greedy', 'Heap (Priority Queue)', 'Python3']