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:
- The bridge is rickety and can hold a maximum of two people at once.
- There is exactly one torch.
- It is dark and too dangerous to cross without a torch.
- The crossing is too long for the torch to be thrown across.
- When two cross, they go at the speed of the slowest.
Task: Minimise the length of time spent for all four to cross.