I tried a greedy approach to solve this question which failed during system testing. I am trying to find proof of incorrectness but am not able to do so. This is my approach.
I first sort vector s(number of customers for each item in reverse order) and start from assigning items with most customers. I have an array a[] which stores the number of items bought by customer i. In each iteration, I sort a[]. For each item s[j],I do the following:
- Move in increasing order of a[i] and if a[i]+1 is less than K, then give the item to customer i, (decrease s[j] and move ahead) otherwise break and start assigning that item in decreasing order of a[i].
Can anyone tell when this approach will fail?