Problem #1 MEDIUM
The Bridge at Midnight
Google Amazon Logic
Problem Statement
Four travelers need to cross a rickety bridge at night. The bridge is in such poor condition that it can support at most two people at a time. Because it is pitch black, they must carry a single flashlight to guide their way. Every group crossing the bridge, whether one or two people, must travel at the speed of the slowest person.
The four travelers walk at different speeds: Alice takes 1 minute to cross, Bob takes 2 minutes, Charlie takes 5 minutes, and Daniel takes 10 minutes.
What is the absolute minimum time required for all four travelers to cross to the other side?
Answer & Quick Explanation
Think you've got it? Click below to check your answer.
The minimum time required is 17 minutes by sending the two fastest travelers first, having the fastest return, and then sending the two slowest travelers together.
Detailed Editorial Solution
Want to see the step-by-step breakdown? Click below to reveal the editorial.
To solve this riddle, we must avoid the common temptation of always sending the fastest traveler (Alice) back and forth. If we always send Alice back, the total time would be: Bob+Alice + Charlie+Alice + Daniel+Alice = 2 + 1 + 5 + 1 + 10 = 19 minutes.
Instead, we can save time by having the two slowest travelers (Charlie and Daniel) cross the bridge together, so their times overlap. However, this means we need someone else already on the other side to bring the flashlight back.
Here is the optimal sequence:
1. Alice (1m) and Bob (2m) cross first. (Time elapsed: 2 minutes)
2. Alice (1m) returns with the flashlight. (Time elapsed: 3 minutes)
3. Charlie (5m) and Daniel (10m) cross together. (Time elapsed: 13 minutes)
4. Bob (2m) returns with the flashlight. (Time elapsed: 15 minutes)
5. Alice (1m) and Bob (2m) cross together again. (Time elapsed: 17 minutes)
Thus, the minimum total time is 17 minutes.