Arranging a Wine Party

I am sure you would have enjoyed solving last post's puzzle. I know it was a bit tricky, more cause it was from Google Code Jam'08 Onsite Practice Round. Still, we have two correct entries sent by the third day from the date of the post. While Shashank Srikant used a C++ implementation to get the answer, following it up with a well-built logic, Kapil Garg went past the puzzle with a simple yet elegant observation.

The last ball that remain is only BLACK.

You might notice, that the number of white balls in the bag changes only in even numbers. Hence, starting of with a even number of white balls, and doing only transactions that cause changes in even numerals, you can never reach a state of 1 white ball in the bag. Hence, the ball has to be black :)

Well, this week I also came through a good algorithm development question. I still cannot figure out the perfect logic for it. I thought the blog would be great platform to share the problem. And I would be really thankful if someone can send a probable approach.

Mr Winger is having a party. He has a list of guests along with their in-times and out-times from the party. Anytime, a guest enters the party, he is given a glass of wine. The guest returns the glass as soon as he leaves the party. Given the list of guests and their in/out times, can you help Mr X in deciding what is the minimum number of glasses required for his party.

For Eg, if guest 1 comes at time 2units and leaves at time 3units, while guest 2 comes at time 3units, the glass of guest 1 can be given to guest 2 and hence, only 1 glass is needed. On the other hand, had the guest 2 come at time 2units, we would have needed 2 glasses.

I do have one more puzzle over which I am still hitting my head. Lets keep that for the next week.

Till then,

Good Luck,

and Keep puzzling

Regards,

Vivek

nitkkr.vivek@gmail.com