Minimum time to cross the bridge

Question

There are 6 friends A, B, C, D, E and F who want to cross a bridge. However, there are two problems. First, the bridge can only accommodate two persons at a time. Second, it is night and they need the torch every time they cross the bridge (fortunately, they have one). The minimum time required by them to cross the bridge is 4 minutes, 2 minutes, 7 minutes, 11 minutes, 6 minutes and 1 minute, respectively. What is the minimum time in which they would be able to cross the bridge?

Options are - 28 29 30 31

Answer 1

You can solve this as a shortest path problem, as shown here.

For your data, the minimum is

29

attained as follows:

{B,F} cost = max(2,1)  = 2
{F}   cost = max(1)    = 1
{A,E} cost = max(4,6)  = 6
{B}   cost = max(2)    = 2
{B,F} cost = max(2,1)  = 2
{F}   cost = max(1)    = 1
{C,D} cost = max(7,11) = 11
{B}   cost = max(2)    = 2
{B,F} cost = max(2,1)  = 2

Answer 2

There are a bunch of similar problems out there, but here's a specific detailed answer:

Round 0 -> Starting:
- Left side = 1, 2, 4, 6, 7, 11
- Right side = None
- Total time = 0 minutes

Round 1 -> 1 and 2 cross, 1 comes back:
- Left side = 1, 4, 6, 7, 11
- Right side = 2
- Total time = 0 + 2 + 1 = 3 minutes

Round 2 -> 7 and 11 cross, 2 comes back:
- Left side = 1, 2, 4, 6
- Right side = 7, 11
- Total time = 3 + 11 + 2 = 16 minutes

Round 3 -> 1 and 2 cross, 1 comes back:
- Left side = 1, 4, 6
- Right side = 2, 7, 11
- Total time = 16 + 2 + 1 = 19 minutes

Round 4 -> 4 and 6 cross, 2 comes back:
- Left side = 1, 2
- Right side = 4, 6, 7, 11
- Total time = 19 + 6 + 2 = 27 minutes

Round 5 -> 1 and 2 cross:
- Left side = None
- Right side = 1, 2, 4, 6, 7, 11
- Total time = 27 + 2 + 0 = 29 minutes