Bridge and Torch with a Pairing Constraint

Reported in interviews at Virtu Financial WorldQuant

Problem statement

Five people need to cross a bridge at night. They have a single torch, and the bridge is too dangerous to cross without it. At most two people can cross at a time, and when two cross together, they move at the slower person's speed. After each crossing, someone must carry the torch back for the next group.

The five people have crossing times of $1, 2, 5, 8,$ and $12$ minutes. There is one additional constraint: the person with crossing time $12$ refuses to pair with the person with crossing time $1$ -- they will not cross the bridge together under any circumstances.

  1. Find the minimum total time to get all five people across the bridge.
  2. Prove that your solution is optimal.
Show hint

Which people drive the total cost, and is there a way to pay for them less than once each?

Relevant roles: Data Scientist, Applied Scientist, Research Scientist and ML Engineer.

Related free problems