Brain Teasers | River crossing

 Question: 

Four people, A, B, C and D need to get across a river. The only way to cross the river is by an old bridge, which holds at most 2 people at a time. Being dark, they can't cross the bridge without a torch, of which they only have one. So each pair can only walk at the speed of the slower person. They need to get all of them across to the other side as quickly as possible. A is the slowest and takes 10 minutes to cross, B takes 5 minutes, C takes 2 minutes, and D takes 1 minute. What is the minimum time to get all of them across to the other side? 

 

Solution: 

 

If we start with A and B then we will not be able to find the minimum time because although A and B can go together then one of them will have to come back with the torch which will lead to excess time.(10 min + 5 min) 

 

If we start with A and C or D then also we will not find an optimal combination as B will be left behind and then we will not be able to reduce the time that we do in case we send A and B together. 

 

We will start with C and D as they take the least time. 

We will send C and D (2 min) together to the other side. 

Now D (1 min) will come back 

Then A and B (10 min) can go back together 

Now C (2 min) will come back 

 

Finally, C and D (2 min) can cross the bridge together. 

 

Minimum time to get all of them across to the other side: 

= Max(2min,1min) + 1min + Max(5min,10min) + 2min + Max(2min,1min) 

= 2 + 1 + 10 + 2 + 2  

= 17 minutes