Greedy C++ & Java
Btw, the question is excatly the same as the one I published before.\n\n\nhttps://leetcode.com/discuss/interview-question/3624545/GPL-Challenge-Q1\n\n\n# Intuit
Btw, the question is excatly the same as the one I published before.\n\n\n[https://leetcode.com/discuss/interview-question/3624545/GPL-Challenge-Q1](https://leetcode.com/discuss/interview-question/3624545/GPL-Challenge-Q1)\n\n\n# Intuition\nGreedy algorithm\n\n\n(1) sort the items by the profit (items[.][0]) in non increasing order.\n(2) select the first k items according non-increasing sorted profit (items[.][0]).\n(3) For remaining unselected items, try using them one by one (in the non increasing of profit order) to replace the selected ones.\n\nConditions for replacing:\n(a) The items to be replaced\'s category must not be unique in selected items. Namely, removing it doesn\'t reduce the number of categories.\n(b) The items to be replaced must have the minimum profit (items[.][0] value) in the selected items when condition (a) is satisified.\n(c) The new item to replace the original selected one must have a new category. Namely we use an item with lower profit (or equal) to increase the number of categories. \n\nWe can maintain the selected items\'s categories using a hash map.\n\n# Approach\nUse priority queue & hashmap to maintain the profits and categories.\n\n# Complexity\n- Time complexity:\nO(nlogn)\n\n- Space complexity:\nO(n)\n\n# Code\nC++\n```\nclass Solution {\n    long long sqr(long long x) {\n        return x * x;\n    }\n\npublic:\n    long long findMaximumElegance(vector<vector<int>>& items, int k) {\n        const int n = items.size();\n        vector<int> ind(n);\n        for (int i = 0; i < n; ++i) {\n            ind[i] = i;\n        }\n        sort(ind.begin(), ind.end(), [&](const int x, const int y) {\n            return items[x][0] > items[y][0];\n        });\n        unordered_map<int, int> num;\n        priority_queue<pair<int, int>> q;\n        long long v = 0;\n        for (int i = 0; i < k; ++i) {\n            v += items[ind[i]][0];\n            ++num[items[ind[i]][1]];\n            q.push({-items[ind[i]][0], ind[i]});\n        }\n        long long r = v + sqr(num.size());\n        for (int i = k; i < n && !q.empty(); ++i) {\n            if (num.count(items[ind[i]][1])) {\n                continue;\n            }\n            const int x = q.top().second;\n            q.pop();\n            if (num[items[x][1]] == 1) {\n                --i;\n                continue;\n            }\n            v += items[ind[i]][0] - items[x][0];\n            --num[items[x][1]];\n            ++num[items[ind[i]][1]];\n            r = max(r, v + sqr(num.size()));\n        }\n        return r;\n    }\n};\n```\nJava:\n```\nclass Solution {\n    long sqr(long x) {\n        return x * x;\n    }\n\n    public long findMaximumElegance(int[][] items, int k) {\n        final int n = items.length;\n        Integer[] ind = new Integer[n];\n        for (int i = 0; i < n; ++i) {\n            ind[i] = i;\n        }\n        Arrays.sort(ind, new Comparator<Integer>() {\n            @Override\n            public int compare(Integer x, Integer y) {\n                return Integer.compare(items[y][0], items[x][0]);\n            }\n        });\n        Map<Integer, Integer> num = new HashMap<>();\n        PriorityQueue<Pair<Integer, Integer>> q = new PriorityQueue<>(new Comparator<Pair<Integer, Integer>>() {\n            @Override\n            public int compare(Pair<Integer, Integer> p1, Pair<Integer, Integer> p2) {\n                return Integer.compare(p2.getKey(), p1.getKey());\n            }\n        });\n        long v = 0;\n        for (int i = 0; i < k; ++i) {\n            v += items[ind[i]][0];\n            num.put(items[ind[i]][1], num.getOrDefault(items[ind[i]][1], 0) + 1);\n            q.add(new Pair<>(-items[ind[i]][0], ind[i]));\n        }\n        long r = v + sqr(num.size());\n        for (int i = k; i < n && !q.isEmpty(); ++i) {\n            if (num.containsKey(items[ind[i]][1])) {\n                continue;\n            }\n            int x = q.peek().getValue();\n            q.poll();\n            if (num.get(items[x][1]) == 1) {\n                --i;\n                continue;\n            }\n            v += items[ind[i]][0] - items[x][0];\n            num.put(items[x][1], num.get(items[x][1]) - 1);\n            num.put(items[ind[i]][1], num.getOrDefault(items[ind[i]][1], 0) + 1);\n            r = Math.max(r, v + sqr(num.size()));\n        }\n        return r;\n    }\n}\n```
['C++', 'Java']