14
$\begingroup$

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?

| improve this question | |
$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Trenin Dec 17 '14 at 15:39
  • 3
    $\begingroup$ 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. $\endgroup$ – Joe Z. Dec 17 '14 at 19:43
  • $\begingroup$ 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." $\endgroup$ – Colonel Panic Jul 4 '16 at 10:41
18
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – Hao Ye Dec 18 '14 at 5:22
  • $\begingroup$ optimum solution, i tried hard but couldn't beat 39 $\endgroup$ – kavi temre Jun 29 '15 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.