Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.
Greedy Algorithm Problem: Blocks and Containers
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 · ·