There is a group of n people with speeds s1, ..., sn. They have a conference that starts soon and they must all cross a bridge to get there. All n people begin on the same side of the bridge. It is nighttime and there is only one flashlight. A maximum of two people can cross at one time.

Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown. A pair must walk together at the rate of the slower man's race.

1) Provide a greedy algorithm to get all these n people across the bridge in a fastest way.
2) Describe the algorithm briefly
3) Prove the correctness
4) Give the optimal substructure
5) Analyze the time cost of your schedule.