[Java] Greedy solution
Intuition\n\nGreedy works here. \n\nIdea: we firstly pick k items with max total profits. Then we gradully/greedily remove some of them and replace with ones in
# Intuition\n\nGreedy works here. \n\nIdea: we firstly pick `k` items with max total profits. Then we gradully/greedily remove some of them and replace with ones in different categories. This way, the `total_profit` decreases, but we are compensated by `distinct_categories^2`, and we may get a bigger elegance value. Above process will be stopped until all categories are used.\n\n\n# Code\n```\nclass Solution {\n    public long findMaximumElegance(int[][] items, int k) {\n        Set<Integer> distinct = new HashSet<>();\n        for (int[] item : items) {\n            distinct.add(item[1]);\n        }\n\n        Arrays.sort(items, Comparator.comparingInt(i -> -i[0]));\n\n        long maxElegance = 0;\n        Map<Integer, Integer> picked = new HashMap<>();\n\n        for (int i = 0; i < k; i++) {\n            maxElegance += items[i][0];\n            picked.put(items[i][1], picked.getOrDefault(items[i][1], 0) + 1);\n        }\n        maxElegance += (long) picked.size() * picked.size();\n\n        int last = k - 1;\n        long runningElegance = maxElegance;\n        for (int i = k; i < items.length && picked.size() < distinct.size() && last >= 0; i++) {\n            if (picked.containsKey(items[i][1])) {\n                continue;\n            }\n\n            for ( ; last >= 0; last--) {\n                if (picked.get(items[last][1]) > 1) {\n                    break;\n                }\n            }\n\n            if (last < 0) {\n                return maxElegance;\n            }\n\n            runningElegance = runningElegance - items[last][0] + items[i][0];\n            long size = picked.size();\n            runningElegance += ((size + 1) * (size + 1)) - size * size;\n            if (runningElegance > maxElegance) {\n                maxElegance = runningElegance;\n            }\n            picked.put(items[last][1], picked.get(items[last][1]) - 1);\n            picked.put(items[i][1], 1);\n            last--;\n        }\n\n        return maxElegance;\n    }\n}\n```
['Java']