Greedy Stupid Bruteforce Python O(n*max(k, log(n)) )
Main method sorts list and divides it on left and right (k+1) times. Calc() function tries to greedilly to distribute elements of each part into 0 to k subsets:
Main method sorts list and divides it on left and right (k+1) times. Calc() function tries to greedilly to distribute elements of each part into 0 to k subsets:\n```\nclass Solution:\n    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n        nums.sort()\n        maxi = (nums[-1] - nums[0] ) * k + 1\n        ans = maxi\n        n = len(nums)\n        pack = n // k\n        for i in range(k+1):\n            l = self.calc(nums[0:i*pack], i)\n            r = self.calc(nums[i*pack:], k-i)\n            if l >= 0 and r >= 0:\n                res = l + r\n                print(i, res)\n                ans = min(ans, res)\n        \n        if ans == maxi: return -1\n        return ans\n        \n    def calc(self, nums: List[int], k: int) -> int:\n        if not nums or not k: return 0\n        \n        c = collections.Counter(nums)\n        keys = sorted(c.keys())\n        if max(c.values()) > k: return -1\n        ans, l, r, s = 0, 0, 0, 0\n        pack = len(nums) // k\n        n = len(nums)\n        pq = []\n        for subset in range(k):\n            include = []\n            size = len(c)\n            for i in keys:\n                if i not in c: continue\n                if k-subset == c[i] or size == pack:\n                    include.append(i)\n                    c[i] -= 1\n                else:\n                    size -= 1            \n            \n            ans += include[-1] - include[0]\n            \n            for j in include:\n                if c[j] == 0:\n                    del c[j]\n            \n        return ans\n```\n
[]