救生艇问题如何用贪心求最少船数？（LeetCode 881）

简化版

先按体重排序，每次让最重的人上船；如果最轻的人能和他同船，就一起走，否则最重的人单独走。

这是最优的，因为最重的人迟早要占一条船，把他和当前最轻的人配对不会浪费更好的机会。

详细版

排序后用双指针 l 指向最轻的人，r 指向最重的人。每轮一定安排 people[r] 上船。如果 people[l] + people[r] <= limit，说明最轻可以和最重同船，l++；无论是否配对，最重都已上船，所以 r--，船数加 1。

int numRescueBoats(int[] people, int limit) {
    Arrays.sort(people);
    int l = 0, r = people.length - 1;
    int ans = 0;
    while (l <= r) {
        if (people[l] + people[r] <= limit) l++;
        r--;
        ans++;
    }
    return ans;
}

如果最轻的人都不能和最重的人同船，那么任何其他人更重，也不可能和最重的人同船，最重只能单独走。如果能配，则把最轻的人带走一定不吃亏。

完整版教学

一、为什么先处理最重的人

每条船最多坐两个人，且有重量上限。最重的人是最难安排的，因为他能搭配的人最少。如果不先安排他，后面只会剩下更有限的选择，不会凭空变容易。

贪心中经常要先处理「约束最紧」的对象。救生艇里约束最紧的就是最重的人：他不能被拆分，也不能和超过限制的人同船，所以每轮先决定他的归宿。

二、为什么尝试搭配最轻的人

当最重的人 H 上船时，能和他同船的人必须满足 weight + H <= limit。排序后，最轻的人 L 是最容易满足这个条件的候选。如果连 L + H 都超过限制，那么其他任何人都不可能和 H 同船。

如果 L + H <= limit，把最轻的人和最重的人配在一起不会变差。因为最轻的人对任何船都是最容易安插的，他和最重的人同船可以节省一个位置，同时不会抢走其他人更需要的轻量伙伴。

三、交换论证证明贪心安全

假设存在一个最优方案中，最重的人 H 没有和当前最轻的人 L 坐同一条船。如果 H 单独坐，而 L 和别人坐，那么把 L 挪去和 H 坐，不会超重，船数不增加。如果 H 和另一个人 X 坐，且 L <= X，那么把 X 换成 L 也不会超重。

这说明当 L + H <= limit 时，总存在一个最优方案让 L 和 H 同船。因此贪心配对是安全的，不会排除最优解。

四、数字例子完整走查

以 people = [3,2,2,1]，limit = 3 为例，排序后是 [1,2,2,3]。

l 指向	r 指向	判断	船数
1	3	`1+3>3`，3 单独走	1
1	2	`1+2<=3`，1 和 2 同船	2
2	2	剩下 2 单独走	3

答案是 3。注意第一轮最轻的 1 都无法和 3 同船，所以 3 不可能和任何人同船。

五、流程示意

排序: [轻 ... 重]
       l       r

while l <= r:
  安排 people[r]
  如果 people[l] + people[r] <= limit:
      l++   // 最轻一起走
  r--       // 最重一定走
  boats++

这个流程每轮至少送走一个人，最多送走两个人。双指针不会回退，所以排序后扫描是线性的。

六、复杂度与边界

排序是主要成本，时间 O(n log n)。双指针扫描一次，空间取决于排序实现，额外变量是 O(1)。如果输入体重范围很小，可以用计数排序或桶计数优化排序成本，但面试里普通排序足够。

边界上，若只剩一个人，l == r 时仍然需要一条船。题目通常保证每个人体重不超过 limit，否则单人也无法上船，业务题中需要额外处理。

记忆钩子：最重的人每轮必须走；能带最轻就带，带不了谁都带不了。

七、常见误区与追问

误区：优先让最轻的人配最重能配的人。 更稳定的视角是先固定最重的人，因为他选择最少。
误区：一条船可以坐多人。 原题限制最多两人，这是双指针贪心成立的重要条件。
误区：配不上最轻时还尝试中间的人。 中间的人更重，不可能比最轻更容易配上最重。
追问：为什么配最轻不会影响最优？ 可用交换论证，把最重原来的搭档换成更轻的人不会超重。
追问：复杂度是多少？ 排序 O(n log n)，扫描 O(n)，总时间 O(n log n)。
追问：如果船可坐任意多人呢？ 问题会变成装箱类问题，当前简单贪心不再保证最优。

八、加强记忆

救生艇问题的锚点是「先安排最难安排的最重者」。每轮最重的人一定要上船；如果当前最轻的人能一起上，就把他带走，因为不会损害最优；如果最轻都带不了，最重只能单独走。排序让「最轻」和「最重」一眼可见，双指针让每个人只处理一次。记住「最重必走，最轻试配」，代码和证明都会自然出来。

简化版

详细版