经典面试题5 - 过桥时间

过桥

问题:

有四个人需要在漆黑的夜晚过一个破旧的木桥，不幸的是，破旧的桥最多只能支持2个人同时过桥，而由于是在夜晚他们需要使用仅有的一个手电筒才能安全过桥，并且每个人过桥的时间也是不同的，分别是 1分钟，2分钟，7分钟和10分钟。请问四个人全部安全通过这座桥最短需要多长时间？

答案：

最直接的思路应是让过桥最快的人作为领航员带领每个人一起过桥，这样需要多少时间呢？
10 + 1 + 7 + 1 + 2 =21分钟。

真的是这样吗？当然不是，不然也太简单了。

让我们头脑风暴一下，为了减少过桥总时间，我们应该让10 和 7同时过桥，如果他们同时过桥，那需要其中的一个返回去接剩下的人（送手电筒）。

这明显不是我们想要的结果，很奇怪我们为什么会这么想？ 也许我们可以让 1 先等在那边，然后把手电筒带回来。

哈哈，这已经非常接近答案了！

最快的办法就是让 1 过桥并返回，然后让2作为导航员再把1带领过桥。

整体策略就出来了：

• 1 和 2过桥，2 返回
• 7 和 10 过桥，1 返回
• 1 和 2一起过桥 (结束)

合计时间 = 2 + 2 + 10 + 1 + 2 = 17 分钟

<blockquote> 如果你真的看懂了，请点赞。 </blockquote>

推荐阅读

经典面试100题 - 持续更新中