[C++/Python] Easy Greedy Solution | beats 100 percent
Intuition\n Describe your first thoughts on how to solve this problem. \nTry to optimise between these two\n- Use items with maximum profits\n- Use items of max
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTry to optimise between these two\n- Use items with maximum profits\n- Use items of maximum distinct categories\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nStarted with adding all the items with maximum profits in the default elegance.\nUse minheap to Store all the duplicates used\n\nReplace duplicates and use items from categories which are yet to be used in greedy way using priority queue\n\n# Complexity\n- Time complexity: O(nlogn)\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# C++ Code\n```\nclass Solution {\npublic:\n    long long findMaximumElegance(vector<vector<int>>& items, int k) {\n        sort(items.begin(),items.end(),greater<vector<int>>());\n        \n        int n=items.size(),i;\n        vector<int> cat_used(n+1,0);\n        \n        priority_queue<int,vector<int>,greater<int>> duplicates_min;\n        // Include first k items having maximum profit in elegance\n        long long elegance=0;\n        for(i=0;i<k;i++){\n            elegance+=items[i][0];\n            if(++cat_used[items[i][1]]>1){\n                duplicates_min.push(items[i][0]);\n            }\n        }\n        long long distinct_categories = (k-duplicates_min.size()); \n        elegance+=distinct_categories*distinct_categories;\n        \n        long long ans=elegance;\n        \n        if(duplicates_min.empty())return ans;\n\n        // Finding other categores which are not included in elegance and store maximum of them\n        for(;i<n;i++){\n            // first occurance of any category will be maximum of them. Since, items are sorted\n            if(++cat_used[items[i][1]]==1){\n                elegance += (long long)(items[i][0]-duplicates_min.top());\n                // elegance += (distinct_categories + 1)^2 - distinct_categories^2\n                elegance += (2*distinct_categories + 1); \n                ans=max(ans,elegance);\n\n                duplicates_min.pop();\n                if(duplicates_min.empty())return ans;\n\n                distinct_categories++;\n            }\n        }\n        return ans;\n    }\n};\n```\n# Python Code\n```\nimport heapq\n\nclass Solution:\n    def findMaximumElegance(self, items, k):\n        items.sort(reverse=True)\n\n        n = len(items)\n        cat_used = [0] * (n + 1)\n\n        duplicates_min = []\n        left_categories_max = []\n        elegance = 0\n\n        for i in range(k):\n            elegance += items[i][0]\n            cat_used[items[i][1]] += 1\n            if cat_used[items[i][1]] > 1:\n                heapq.heappush(duplicates_min, items[i][0])\n\n        distinct_categories = k - len(duplicates_min)\n        elegance += distinct_categories * distinct_categories\n\n        ans = elegance\n\n        if not duplicates_min:\n            return ans\n\n        i = k\n\n        while i < n:\n            if cat_used[items[i][1]] == 0:\n                elegance += items[i][0] - heapq.heappop(duplicates_min)\n                elegance += 2 * distinct_categories + 1\n                ans = max(ans, elegance)\n\n                if not duplicates_min:\n                    return ans\n\n                distinct_categories += 1\n\n            cat_used[items[i][1]] += 1\n            i += 1\n\n        return ans\n\n```\n\n\n
['Greedy', 'Sorting', 'Heap (Priority Queue)', 'C++']