Three people need to cross a weak bridge at night. They have just one turn and the bridge is only strong enough to support two people at a time. Not all people take the same time to cross the bridge. Times for each person: 2 min, 5 mins and 7 mins. What is the shortest time for all three of them to cross the bridge?
2026 Update: Bridge Crossing Optimization — Greedy Strategy
N people must cross a bridge at night with one torch. At most 2 cross at a time. Two together move at the slower person’s speed. Minimize total crossing time. The optimal strategy compares two approaches at each step.
def min_bridge_crossing(times: list) -> int:
"""
Find minimum time for all n people to cross.
Returns total time.
Two candidate strategies (for groups of 4+):
Strategy A: Fastest escorts slowest, then returns, then escorts second slowest
Cost: times[-1] + times[0] + times[-2] + times[0]
= times[-1] + times[-2] + 2*times[0]
Strategy B: Two fastest cross first, fastest returns, two slowest cross together, second fastest returns
Cost: times[1] + times[0] + times[-1] + times[1]
= times[-1] + times[-2] + ... wait, let's recount:
t=0: fastest two cross: cost=times[1]
Return: fastest comes back: cost=times[0]
Two slowest cross: cost=times[-1]
Return: second fastest comes back: cost=times[1]
Total: 2*times[1] + times[0] + times[-1]
"""
times = sorted(times)
n = len(times)
if n == 1:
return times[0]
if n == 2:
return times[1]
if n == 3:
# Only one reasonable strategy: fastest escorts both
# t1: fastest+second cross, fastest returns -> times[1]+times[0]
# t2: fastest+slowest cross -> times[2]
return times[0] + times[1] + times[2]
total = 0
while n > 3:
# Strategy A: use fastest (times[0]) as escort for each of the two slowest
strategy_a = times[-1] + times[-2] + 2 * times[0]
# Strategy B: send two slowest together after two fastest cross
strategy_b = 2 * times[1] + times[0] + times[-1]
total += min(strategy_a, strategy_b)
n -= 2 # Two slowest have crossed
# Handle remaining 1, 2, or 3 people
if n == 3:
total += times[0] + times[1] + times[2]
elif n == 2:
total += times[1]
else:
total += times[0]
return total
# Test cases (well-known answers)
cases = [
([1, 2, 5, 8], 15),
([1, 2, 5, 10], 17),
([1, 2], 2),
([1, 5, 10], 16),
([1, 2, 3], 6),
]
for times, expected in cases:
result = min_bridge_crossing(times)
status = "OK" if result == expected else "FAIL"
print(f"{status}: times={times}, result={result}, expected={expected}")
# Intuition for when to use each strategy:
def strategy_choice(times):
times = sorted(times)
strat_a = times[-1] + times[-2] + 2 * times[0]
strat_b = 2 * times[1] + times[0] + times[-1]
if strat_a < strat_b:
return "A (escort each slow person individually)"
else:
return "B (send two slow people together)"
print(strategy_choice([1, 2, 5, 10])) # B (17 vs 18)
print(strategy_choice([1, 5, 6, 10])) # A (23 vs 22 -- use A when slowest two are close in speed)
Key insight: The greedy strategy works because the problem has optimal substructure — after safely crossing the two slowest people, the remaining subproblem is identical to the original with fewer people. Strategy B is better when times[-1] + times[-2] (cost of sending two slowest) is much less than 2 * times[-2] (cost of escorting them one by one). When times[1] - times[0] < times[-2] - times[-1], prefer A.