[Python3] greedy, time: O(n*lg(n) +  k*n), with explaination
\nI tried two directions greedily, from large numbers to small numbers, and small numbers to large numbers.\n\nTry both direction and then pick the min of two c
\nI tried two directions greedily, from large numbers to small numbers, and small numbers to large numbers.\n\nTry both direction and then pick the min of two candidates.\n\nLet\'s explain small-to-large direction first.\n\n1. Build a counting table, and sort the keys.\n2. First reject those test cases where some numbers appear more than k times.\n3. For those numbers appear exactly `k` times, put them to each group, one to one.\n4. Pick distinct numbers, from small to large, putting them into the first group until it is full. \n5. For those numbers smaller than those in `step 4`, If their counts `== k-1` , we shall put them to the remaining `k-1` groups, one to one.\n\nRepeat until we fill all groups.\nThen try the large-to-small direction again.\n\nApparently the two directions will give different partitioning, so I just take the smallest. Not sure if it is a valid method, or just lucky on those test case.\n\nHope someone could give more intuition or proof of the correctness/incorrectness.\n\n`n lg n` comes from sorting.\n`k*n` comes from for-loop, for worst case that we have all distinct numbers.\n\ntime: 20~36 ms\t\nspace: 14.1~14.3 MB\n\n```\ndef minimumIncompatibility(self, nums: List[int], k: int) -> int:\n\tdef helper(to_reverse):\n\t\tcc = Counter(nums)\n\t\tif cc.most_common()[0][1] > k:  # if a num more than k times, cant do\n\t\t\treturn -1\n\n\t\tif to_reverse:\n\t\t\tli = sorted(cc.keys())\n\t\telse:\n\t\t\tli = sorted(cc.keys(), reverse=True)\n\n\t\tm = len(nums) // k\n\t\tn = len(nums)\n\n\t\tstacks = [[] for _ in range(k)] # k stacks for each group\n\t\tself.i = 0  # to indicate the st we will append to\n\n\t\tdef put(x):\n\t\t\tif len(stacks[self.i]) == m:\n\t\t\t\tself.i += 1\n\t\t\tstacks[self.i].append(x)\n\n\t\tdef put_many(x): # put to each group\n\t\t\tfor _i in range(self.i + 1, k): # put to all after stacks\n\t\t\t\tstacks[_i].append(x)\n\n\t\tput_count = 0  # count how many times we put\n\n\t\t# for those numbers w/ k counts\n\t\tfor x in li:\n\t\t\tif cc[x] == k:\n\t\t\t\tfor _i in range(self.i, k): \n\t\t\t\t\tstacks[_i].append(x)\n\t\t\t\tput_count += k\n\t\t\t\tcc[x] = 0\n\n\t\twhile put_count < len(nums):\n\t\t\talready_put = False  # already put a num in this for-loop\n\t\t\tfor x in li:\n\t\t\t\tif already_put and len(stacks[self.i]) == m:  # if this group full, check the remaining numbers to see if they need to be partitioned into each group\n\t\t\t\t\tif cc[x] == k - self.i - 1:\n\t\t\t\t\t\tput_many(x)\n\t\t\t\t\t\tput_count += k - self.i - 1\n\t\t\t\t\t\tcc[x] = 0\n\t\t\t\telif cc[x] > 0:  # put number to group in order\n\t\t\t\t\tput(x)\n\t\t\t\t\tput_count += 1\n\t\t\t\t\tcc[x] -= 1\n\t\t\t\t\talready_put = True\n\n\t\treturn sum([max(st) - min(st) for st in stacks])  # compute the incompatibility\n\n\treturn min(helper(True), helper(False))  \n```
[]