# Fastest way to cross a river: four people with different rowing speeds

This problem is commonly cited as a Microsoft interview problem, although I have paraphrased it here to involve a river and a boat instead of a bridge and a flashlight, and tweaked the crossing times a little bit.

There are four people standing on one side of a river, and they need to cross it as quickly as possible to the other side. However, there is only one rowboat docked at the river's bank, and only two people can fit in it. These four people can row to the other side in 3, 7, 12 and 15 minutes, and if two people cross, they must row at the rate of the slower person. How can these four people cross as quickly as possible, and how long will it take them?

• Since you've changed it to a boat, the premise no longer makes sense. Why would two people have to row only as fast as the slowest? You'd think that two people can row faster than either individually. The puzzle makes more sense in its original form where they must walk. Dec 17, 2014 at 15:39
• I could probably make an argument that each person can only hold one oar and if they row at different rates the boat would spin around instead of going forward.
– user88
Dec 17, 2014 at 19:43
• Popularly known as the bridge and torch problem. The important constraint is "when two people cross the bridge together, they must move at the slower person's pace." Jul 4, 2016 at 10:41

You'll want the two slowest people to cross together, but you'll also want one fast person on either side to bring the boat back quickly. So I believe this will do it (I labeled the people from A (fastest) to D (slowest)):

1. A and B cross (7 mins)
2. A returns (3 mins)
3. C and D cross (15 mins)
4. B returns (7 mins)
5. A and B cross (7 mins)

This takes a total of 39 minutes. Note that steps 2 and 4 are interchangeable.

• To demonstrate optimality, steps 1, 3, and 5 send two people over, the minimum here is 15+7+7. Steps 2 and 4 send 1 person back each time, the minimum here is 3+7 (cannot send A back twice). Dec 18, 2014 at 5:22
• optimum solution, i tried hard but couldn't beat 39 Jun 29, 2015 at 15:19
• @arshajii , what was the intuition behind your answer ? Did you solve it by brute force ? Oct 21, 2020 at 21:23
• @HemantAgarwal The main idea is that you want to overlap the "slowness" of the two slower people to avoid paying for it twice. Therefore, the two slowest people should cross together. At the same time, the boat needs to be returned, so it is good to have a fast person on both sides. That's what gives rise to this answer (of course it isn't a rigorous proof or anything). Oct 21, 2020 at 22:01