✅ Beat 100% | ✨ O(N + k log k) | 🏆 Most Efficient Solution | 💯 Simple Greedy
Intuition\n Describe your first thoughts on how to solve this problem. \n  * For each category, we would always pick the items with the largest profits.\n  * If
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n  * For each category, we would always pick the items with the largest profits.\n  * If we picked any item in a category, we say we "picked this category".\n  * The `max_profit` for each category is a key. Assume we sorted categories by this key, we would never pick a "smaller category" when a larger category is not picked.\n  * The above intuition tells us that we would always pick the largest $k\'$ categories where $k\' \\le k$.\n  * This problem is asking for a balanced between "more total profits" and "more distinct categories".\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe first pick the largest `total_profit`, then gradually\n  * remove the smallest item which is in a category that has more than one items picked (so that the `distinct_categories` does not go down)\n  * at the same time pick a new category.\n \nThe best answer will be found during this greedy process.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$\\Theta(N + k \\log k)$$\nWe only need to sort the largest k of them.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$\\Theta(N)$$\n\n# Code\n```\nstruct Category {\n  int id = 0;\n  int max_profit = -1;\n\n  bool operator<(const Category& other) const {\n    return max_profit < other.max_profit;\n  }\n};\n\nstruct Profit {\n  int profit;\n  int category;\n\n  bool operator<(const Profit& other) const {\n    return profit < other.profit;\n  }\n};\n\ntemplate <typename T>\nvoid SortLastN(vector<T>& data, int n) {\n  auto mid = data.end() - n;\n  std::nth_element(data.begin(), mid, data.end());\n  std::sort(mid, data.end());\n}\n\nclass Solution {\npublic:\n  long long findMaximumElegance(vector<vector<int>>& items, int k) {\n    const int N = items.size();\n\n    vector<Category> categories(N + 1);\n    vector<Profit> profits;\n    profits.reserve(N);\n    for (const vector<int>& item : items) {\n      int profit = item[0];\n      int category = item[1];\n      categories[category].id = category;\n      categories[category].max_profit = max(categories[category].max_profit, profit);\n      profits.push_back({.profit = profit, .category = category});\n    }\n\n    SortLastN(profits, k);\n    SortLastN(categories, k);\n\n    int64_t total_profit = 0;\n    int distinct_categories = 0;\n    vector<int> counts(N + 1);  // # of items we used for each category.\n    for (int i = profits.size() - k; i < profits.size(); ++i) {\n      total_profit += profits[i].profit;\n      distinct_categories += ++counts[profits[i].category] == 1;\n    }\n    // Base case: pick the largest k items.\n    int64_t answer = total_profit +\n        static_cast<int64_t>(distinct_categories) * distinct_categories;\n\n    for (int i = profits.size() - k; i < profits.size() && distinct_categories < k; ++i) {\n      int& count = counts[profits[i].category];\n      if (count == 1) {\n        continue;\n      }\n      total_profit -= profits[i].profit;\n      --count;\n\n      while (counts[categories.back().id] > 0) {  // We need a new category\n        categories.pop_back();\n      }\n      if (categories.back().max_profit < 0) {\n        break;  // No more new category exists.\n      }\n      total_profit += categories.back().max_profit;\n      ++distinct_categories;\n      categories.pop_back();\n\n      // Now we removed one item and added one more category.\n      // We did this greedily:\n      //   * Removed the smallest items in use while not reducing `distinct_categories`.\n      //   * Added a new category with largest single item profit.\n      answer = max(answer, total_profit +\n          static_cast<int64_t>(distinct_categories) * distinct_categories);\n    }\n    return answer;\n  }\n};\n```
['Greedy', 'Quickselect', 'C++']