logical deduction - 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?

Answer

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.