Efficient Way To Cross The River
What's the challenge?
Let's name each person by their crossing times as 1,2,7,10.
The instant solution that everyone can think of is using 1 as a usher to guide all. That means 10 & 1 goes, 1 comes back; 7 & 1 goes again 1 comes back and 2& 1 goes finally. This would take 10 + 1 + 7 + 1 + 2 = 21 mins to cross rivers.
Is it really efficient solution? What if we find a way to cross both 10 & 7 in one go & other 1 waiting across to bring back torch.
1. The 1 & 2 goes across but 1 comes back - 2 + 1 = 3 mins required.
2. Now 10 & 7 goes across & send 2 back with torch - 10 + 2 = 12 mins required.
3. Finally after coming back 2 & take 1 across the river - 2 minutes required.
So total 3 + 12 + 2 = 17 minutes required to cross the river for those 4 persons. In first step, 2 can also come back & send 10 & 7. In that case, in second step, 1 has to come back to take 2 across the river. Isn't this a more practical solution?
