# Reduction of a bridge crossing problem

I came across a bridge crossing problem. It got me wondering: Can it be reduced to some sort of scheduling problem. If not, is there any other general problem it can be reduced to?

Here is the problem:

John, Paul, George and Ringo are standing at one end of a bridge crossing. All four must get to the other side. Each can cross in 1, 2, 5 and 10 minutes respectively. There are the following constraints:

1. The bridge is rickety and can hold a maximum of two people at once.
2. There is exactly one torch.
3. It is dark and too dangerous to cross without a torch.
4. The crossing is too long for the torch to be thrown across.
5. When two cross, they go at the speed of the slowest.

Task: Minimise the length of time spent for all four to cross.

• You can phrase this as a shortest path problem. – Yuval Filmus Dec 23 '16 at 14:01
• I see that now. Can it be reduced to any simpler problem? – justinpc Dec 23 '16 at 14:14
• What could be simpler than shortest path? Perhaps you are looking for a more efficient reduction. – Yuval Filmus Dec 23 '16 at 14:59
• Yes, I meant a problem for which a more efficient solution exists. – justinpc Dec 23 '16 at 15:25