Algorithms New World puzzle There are four people who want t

Algorithms:

New World puzzle There are four people who want to cross a bridge; they all begin on the same side. You have 17 minutes to get them all across to the other side. It is night, and they have one flashlight. A maximum of two people can cross the bridge at one time. Any party that crosses, either one or two people, must have the flashlight with them. The flashlight must be walked back and forth; it cannot be thrown, for example. Person 1 takes 1 minute to cross the bridge, person 2 takes 2 minutes, person 3 takes 5 minutes, and person 4 takes 10 minutes. A pair must walk together at the rate of the slower person’s pace. For example, if person 1 and person 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If person 4 returns the flashlight, a total of 20 minutes have passed and you have failed the mission. (Note: According to a rumor on the Internet, interviewers at a well-known software company located near Seattle have given this problem to interviewees.)

Solution

For everone to cross the bridge,

First, Person 1 and Person 2 will cross the bridge. Total time elapsed = 2mins

Then, Person 1 will come back. Total time elapsed = 2+1 = 3mins

Now, Person 3 and Person 4 will cross the bridge. Total time elapsed = 3+10 = 13mins

Now, Person 2 will come back. Total time elapsed = 13+2 = 15mins

Then, Person 1 and Person 2 will cross the bridge. Total time elapsed = 15+2 = 17mins.

So, all 4 persons have crossed the bridge within 17mins.