Hello everyone! I have the following problem and I need to find a greedy algorithm which will solve it:
There are N numbered containers (1...N). In the containers, there are blocks in K-colors, but in all containers there is no more than N blocks of the given color.
Capacity of the i-th container is Pi (it can hold maximum of Pi blocks). Find an algorithm that will rearrange the blocks so that in each container there is at most one block each color. In one step, you are allowed to move only one block from the container to its neighbour (from i-th container, you can move a block to either (i+1)-th or (i-1)-th container, you can also move blocks between 1'st and n-th container).
I'd really appreciate any help. Can anyone give me any clues how to solve this problem using a greedy algorithm?
0 · ·