解决方案

方法：贪心（双指针）

思路

如果最重的人可以与最轻的人共用一艘船，那么就这样安排。否则，最重的人无法与任何人配对，那么他们将自己独自乘一艘船。

这么做的原因是，如果最轻的人可以与任何人配对，那么他们也可以与最重的人配对。

算法

令 people[i] 指向当前最轻的人，而 people[j] 指向最重的那位。

然后，如上所述，如果最重的人可以与最轻的人共用一条船（即 people[j] + people[i] <= limit），那么就这样做；否则，最重的人自己独自坐在船上。

复杂度分析

  • 时间复杂度：，其中 是 people 的长度。

  • 空间复杂度：。