[C++] Sorting + Greedy Analysis
Intuition\n Describe your first thoughts on how to solve this problem. \nWe have two dimensions to this problem at first:\n1. We want to maximize the profit\n2.
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe have two dimensions to this problem at first:\n1. We want to maximize the profit\n2. We want as many distinct categories as possible\n\nSo, we will look for a way to remove one of the dimensions. **We sort the array by non-increasing order of profits (we don\'t need to care about the category in sorting)**. We don\'t have to worry about maximizing the profit because we know **the items in the future will have less or worse than the worst profitable item we have right now.**\n\nWe will look forward to having more distinct categories as we go through the items we haven\'t seen right now.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe start with the first `k` items, so we want to setup the two variables `tot` and `distinct` to calculate the answer. A hash table can be used (in my code I just used a vector of sufficient size) to keep track of how many of the same category items we currently have.\n\nWe also need to keep track of the minimum profit item we have such that **there are other items in the same category**. This is because we want to keep the distinct categories we have **at least the same** (proof of why it works: we have sorted the array in non-increasing order, so if we remove one category, we\'d be adding back a category with a worse profit). We can use a heap to keep track of this.\n\nIMPORTANT: As we add new categories, **we might have a worse answer right now!** (but it may pay off later), so we ensure we don\'t decrease our best answer.\n\n# Complexity\n- Time complexity: $$O(n log n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n  long long findMaximumElegance(vector<vector<int>> &items, int k) {\n    int n = items.size();\n\n    sort(items.begin(), items.end(), greater<vector<int>>{}); // greater profit to least\n\n    long long tot = 0, distinct = 0;\n    vector<int> cnt(n + 1);\n    priority_queue<pair<int, int>> pq; // current minimum profit item\n    for (int i = 0; i < k; i++) {\n      tot += items[i][0];\n      pq.push({-items[i][0], items[i][1]});\n      if (!cnt[items[i][1]]++) distinct++; // first item of a new category\n    }\n\n    long long ans = tot + distinct * distinct;\n    for (int i = k; i < n; i++) {\n      if (cnt[items[i][1]]) continue;\n      // we don\'t want to decrease the amount of distinct categories\n      while (!pq.empty() && cnt[pq.top().second] == 1) pq.pop();\n      // we don\'t have any item to replace without reducing distinct categories, break\n      // this is correct since we have taken the biggest total profit\n      if (pq.empty()) break;\n      // update the variables to take the current item\n      tot = tot + pq.top().first + items[i][0];\n      distinct++;\n      ans = max(ans, tot + distinct * distinct);\n      cnt[pq.top().second]--;\n      pq.pop();\n      cnt[items[i][1]]++;\n      pq.push({-items[i][0], items[i][1]});\n    }\n    return ans;\n  }\n};\n```
['Hash Table', 'Greedy', 'Sorting', 'Heap (Priority Queue)', 'C++']