aloalgoBridge and Flashlight Problem
Hard
You are given a group of people and a bridge. Each person has a specific time it takes for them to cross the bridge. The goal is to find the minimum total time required for all people to cross from one side of the bridge to the other.
Here are the rules:
- At most two people can cross the bridge at any given time.
- A flashlight is required for every crossing. There is only one flashlight.
- When two people cross, they must walk at the pace of the slower person.
- Someone must bring the flashlight back to the starting side for others to cross.
Your task is to implement a function that calculates the minimum total time.
Example 1
Input
[1, 2]
Output
2
Explanation:
The two people (with times 1 and 2) cross together. They move at the speed of the slower person (2 minutes). All people are now on the other side.
Example 2
Input
[1, 2, 5]
Output
8
Explanation:
Sorted times: [1, 2, 5].
- People with times 1 and 2 cross (takes 2 minutes). Flashlight is on the other side.
- Person with time 1 returns with the flashlight (takes 1 minute).
- People with times 1 and 5 cross (takes 5 minutes). All people are now on the other side. Total time = 2 + 1 + 5 = 8 minutes.
Example 3
Input
[1, 2, 5, 10]
Output
17
Explanation:
Sorted times: [1, 2, 5, 10]. This scenario often uses a greedy strategy:
- Fastest (1) and second fastest (2) cross (2 min). Flashlight is on other side.
- Fastest (1) returns with flashlight (1 min).
- Slowest (10) and second slowest (5) cross (10 min). Flashlight is on other side.
- Second fastest (2) returns with flashlight (2 min). (At this point, 5 and 10 are across, 1 and 2 are back on the start side)
- Fastest (1) and second fastest (2) cross (2 min). Total time = 2 + 1 + 10 + 2 + 2 = 17 minutes.
Input
[1, 2]
Output
2