[Java/C++/Python] Sort by Profit
Intuition\nSort items by decresed profiti,\nand we take k first items.\nThis is biggest total_profit we can have.\n\n\n# Explanation\nContinue to iterate the re
# **Intuition**\nSort `items` by decresed `profiti`,\nand we take `k` first items.\nThis is biggest `total_profit` we can have.\n<br>\n\n# **Explanation**\nContinue to iterate the remaining `n - k` items.\nWe can try to take them,\nif this is a new `category` and not in `seen` set.\n\nBut we already have `k` items,\nso we replace one item with smallest `profit`\nwhich has a duplicate `category`.\n\nWe continue doing this,\nuntil every category has no two items.\n\nFinally return the max result.\n<br>\n\n# **Complexity**\nTime `O(nlogn)`\nSpace `O(n)`\n<br>\n\n**Java**\n```java\n    public long findMaximumElegance(int[][] A, int k) {\n        Arrays.sort(A, (a, b) -> b[0] - a[0]);\n        long res = 0, cur = 0;\n        List<Integer> dup = new ArrayList<>();\n        Set<Integer> seen = new HashSet<>();\n        for (int i = 0; i < A.length; ++i) {\n            if (i < k) {\n                if (seen.contains(A[i][1])) {\n                    dup.add(A[i][0]);\n                }\n                cur += A[i][0];\n            } else if (!seen.contains(A[i][1])) {\n                if (dup.isEmpty()) break;\n                cur += A[i][0] - dup.remove(dup.size() - 1);\n            }\n            seen.add(A[i][1]);\n            res = Math.max(res, cur + 1L * seen.size() * seen.size());\n        }\n        return res;\n    }\n```\n**C++**\n```cpp\n    long long findMaximumElegance(vector<vector<int>>& A, int k) {\n        sort(A.begin(), A.end(), [](const vector<int>& a, const vector<int>& b) {\n            return a[0] > b[0];\n        });\n        long long res = 0, cur = 0;\n        vector<int> dup;\n        unordered_set<int> seen;\n        for (int i = 0; i < A.size(); ++i) {\n            if (i < k) {\n                if (seen.count(A[i][1])) {\n                    dup.push_back(A[i][0]);\n                }\n                cur += A[i][0];\n            } else if (seen.find(A[i][1]) == seen.end()) {\n                if (dup.empty()) break;\n                cur += A[i][0] - dup.back();\n                dup.pop_back();\n            }\n            seen.insert(A[i][1]);\n            res = fmax(res, cur + 1L * seen.size() * seen.size());\n        }\n        return res;\n    }\n```\n\n**Python**\n```py\n    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:\n        items = sorted(items, key=lambda v: -v[0])\n        res = cur = 0\n        A = []\n        seen = set()\n        for i, (p, c) in enumerate(items):\n            if i < k:\n                if c in seen:\n                    A.append(p)\n                cur += p\n            elif c not in seen:\n                if not A: break\n                cur += p - A.pop()\n            seen.add(c)\n            res = max(res, cur + len(seen) * len(seen))\n        return res\n```\n
['C', 'Python', 'Java']