🔥 Go Solution | Greedy | Beat 100% | With Explanation🔥
Intuition\nGreedy with regret.\n\n# Approach\nSort the items by profit in descending order and initially select the first k projects. Then, scan through the rem
# Intuition\nGreedy with regret.\n\n# Approach\nSort the `items` by profit in descending order and initially select the first `k` projects. Then, scan through the remaining `items` linearly and assess whether selecting `items[i]` can increase the value of `ans`. During the process, we need to deselect a previously selected item. The optimal strategy is to deselect the item from a category that contains more than one item, as this action will increase the count of `len(categories)` even though it may reduce the `totalProfit`.\n\n# Complexity\n- Time complexity: $$O(n\\text{log}n)$$\n\n- Space complexity: $$O(n)$$\n\n# Code\n```\nfunc findMaximumElegance(items [][]int, k int) int64 {\n\tslices.SortFunc(items, func(a, b []int) int { return b[0] - a[0] })\n\tvar totalProfit int\n\tvisited := make(map[int]bool)\n\tvar duplicate []int\n\tfor _, item := range items[:k] {\n\t\tprofit, category := item[0], item[1]\n\t\ttotalProfit += profit\n\t\tif !visited[category] {\n\t\t\tvisited[category] = true\n\t\t} else {\n\t\t\tduplicate = append(duplicate, profit)\n\t\t}\n\t}\n\tans := totalProfit + len(visited)*len(visited)\n\tfor _, item := range items[k:] {\n\t\tprofit, category := item[0], item[1]\n\t\tif len(duplicate) > 0 && !visited[category] {\n\t\t\tvisited[category] = true\n\t\t\ttotalProfit += profit - duplicate[(len(duplicate)-1)]\n\t\t\tduplicate = duplicate[:(len(duplicate) - 1)]\n\t\t}\n\t\tans = max(ans, totalProfit+len(visited)*len(visited))\n\t}\n\treturn int64(ans)\n}\n```
['Hash Table', 'Stack', 'Greedy', 'Sorting', 'Go']