[Python3] Sorting + Binary search on the number of different categories
[Edit : This worked on all testcases during contest but @canlong found a testcase that my algorithm does not work on]\n\n# Intuition\nThe elegance as a function
[Edit : This worked on all testcases during contest but @canlong found a testcase that my algorithm does not work on]\n\n# Intuition\nThe elegance as a function of the number of distinct categories should look like a mountain with a peak.\n\n# Approach\nBinary search the number of distinct categories by checking the elegance of p distinct categories and p+1 distinct categories.\n\nFor each number of distinct category p, take the categories with the p highest values, then add the greatest values of these p categories that are not the maximum. If there are not enough elements to reach k elements, we need to take additional categories.\n\n# Complexity\n- Time complexity:\nO(n*log(n))\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution:\n    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:\n        dico=defaultdict(list)\n        for profit,category in items:\n            dico[category].append(profit)\n        categories=[]\n        for category in dico:\n            categories.append(sorted(dico[category]))\n        categories.sort(key=lambda x:x[-1],reverse=True)\n        def elegance (distinct):\n            res=0\n            rest=[]\n            for i in range (distinct):\n                res+=categories[i][-1]\n                for j in range (len(categories[i])-1):\n                    rest.append(categories[i][j])\n            rest.sort(reverse=True)\n            if len(rest)<k-distinct:\n                return -1\n            return res+sum(rest[:k-distinct])+distinct**2\n        l,r=1,min(len(categories)-1,k-1)\n        mid=(l+r)//2\n        while l<r:\n            if elegance(mid+1)>elegance(mid) or elegance(mid+1)==-1:\n                l=mid+1\n            else:\n                r=mid\n            mid=(l+r)//2\n        return max(elegance(mid),elegance(mid+1))\n            \n                \n                \n                \n```
['Binary Search', 'Sorting', 'Python3']