Walk the bridge, in pairs as fast a possible

There are 4 women who want to cross a bridge. They all begin on the same side. There is one flashlight. A maximum of two people can cross at one time. It is night. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each woman walks at a different speed. A pair must walk together at the rate of the slower woman's pace.
Woman 1: 1 minute to cross
Woman 2: 2 minutes to cross
Woman 3: 5 minutes to cross
Woman 4: 10 minutes to cross

For example if Woman 1 and Woman 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Woman 4 then returns with the flashlight, a total of 20 minutes have passed and you have failed the mission.


Madhur Kumar Tanwani said...

Hint :

You have 17 minutes to get all of them across to the other side.

Madhur Kumar Tanwani said...

Solution :
The following sequence is the optimized sequence :

STEP 1 :
Pair crossing : W1, W2
Returning : W1
Time spent : 2 + 1 = 3 minutes
Women still to cros : W1, W3, W4

STEP 2 :
Pair crossing : W3, W4 (greedy)
Returning : W2
Time spent : 10 + 2 = 12 minutes
Women still to cros : W1, W2

STEP 3 :
Pair crossing : W1, W2
Returning : none
Time spent : 2 = 2 minutes
Women still to cross : none

Total time : 2 + 12 + 3 = 17 minutes

Madhur Kumar Tanwani said...

Extra bonus :
This problem has been quoted in multiple variants in multiple process scheduling algorithm discussions.

Once such paper : http://www.cs.umass.edu/~mcgregor/papers/04-fun.pdf