英文原文
You are given an array people where people[i] is the weight of the ith person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.
Return the minimum number of boats to carry every given person.
Example 1:
Input: people = [1,2], limit = 3 Output: 1 Explanation: 1 boat (1, 2)
Example 2:
Input: people = [3,2,2,1], limit = 3 Output: 3 Explanation: 3 boats (1, 2), (2) and (3)
Example 3:
Input: people = [3,5,3,4], limit = 5 Output: 4 Explanation: 4 boats (3), (3), (4), (5)
Constraints:
1 <= people.length <= 5 * 1041 <= people[i] <= limit <= 3 * 104
中文题目
第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
示例 1：
输入：people = [1,2], limit = 3 输出：1 解释：1 艘船载 (1, 2)
示例 2：
输入：people = [3,2,2,1], limit = 3 输出：3 解释：3 艘船分别载 (1, 2), (2) 和 (3)
示例 3：
输入：people = [3,5,3,4], limit = 5 输出：4 解释：4 艘船分别载 (3), (3), (4), (5)
提示：
1 <= people.length <= 500001 <= people[i] <= limit <= 30000
通过代码
高赞题解
贪心
一个直观的想法是：由于一个船要么载两人要么载一人，在人数给定的情况下，为了让使用的总船数最小，要当尽可能让更多船载两人，即尽可能多的构造出数量之和不超过 $limit$ 的二元组。
先对 $people$ 进行排序，然后使用两个指针 l 和 r 分别从首尾开始进行匹配：
- 如果 $people[l] + people[r] <= limit$，说明两者可以同船，此时船的数量加一，两个指针分别往中间靠拢；
- 如果 $people[l] + people[r] > limit$，说明不能成组，由于题目确保人的重量不会超过 $limit$，此时让 $people[r]$ 独立成船，船的数量加一，
r指针左移。
我们猜想这样「最重匹配最轻、次重匹配次轻」的做法能使双人船的数量最大化。
接下来，我们使用「归纳法」证明猜想的正确性。
假设最优成船组合中二元组的数量为 $c1$，我们贪心做法的二元组数量为 $c2$。
最终答案 = 符合条件的二元组的数量 + 剩余人数数量，而在符合条件的二元组数量固定的情况下，剩余人数也固定。因此我们只需要证明 $c1 = c2$ 即可。
通常使用「归纳法」进行证明，都会先从边界入手。
当我们处理最重的人 $people[r]$（此时 $r$ 为原始右边界 $n - 1$）时：
- 假设其与 $people[l]$（此时 $l$ 为原始左边界 $0$）之和超过 $limit$，说明 $people[r]$ 与数组任一成员组合都会超过 $limit$，即无论在最优组合还是贪心组合中，$people[r]$ 都会独立成船；
- 假设 $people[r] + people[l] <= limit$，说明数组中存在至少一个成员能够与 $people[l]$ 成船：
- 假设在最优组合中 $people[l]$ 独立成船，此时如果将贪心组合 $(people[l], people[r])$ 中的 $people[l]$ 拆分出来独立成船，贪心二元组数量 $c2$ 必然不会变大（可能还会变差），即将「贪心解」调整成「最优解」结果不会变好；
- 假设在最优组合中，$people[l]$ 不是独立成船，又因此当前 $r$ 处于原始右边界，因此与 $people[l]$ 成组的成员 $people[x]$ 必然满足 $people[x] <= people[r]$。
此时我们将 $people[x]$ 和 $people[r]$ 位置进行交换（将贪心组合调整成最优组合），此时带来的影响包括：- 与 $people[l]$ 成组的对象从 $people[r]$ 变为 $people[x]$，但因为 $people[x] <= people[r]$，即有 $people[l] + people[x] <= people[l] + people[r] <= limit$，仍为合法二元组，消耗船的数量为 $1$；
- 原本位置 $x$ 的值从 $people[x]$ 变大为 $people[r]$，如果调整后的值能组成二元组，那么原本更小的值也能组成二元组，结果没有变化；如果调整后不能成为组成二元组，那么结果可能会因此变差。
对于边界情况，我们证明了从「贪心解」调整为「最优解」不会使得结果更好，因此可以保留当前的贪心决策，然后将问题规模缩减为 $n - 1$ 或者 $n - 2$，同时数列仍然满足升序特性，即归纳分析所依赖的结构没有发生改变，可以将上述的推理分析推广到每一个决策的回合（新边界）中。
至此，我们证明了将「贪心解」调整为「最优解」结果不会变好，即贪心解是最优解之一。
代码：
[]class Solution { public int numRescueBoats(int[] people, int limit) { Arrays.sort(people); int n = people.length; int l = 0, r = n - 1; int ans = 0; while (l <= r) { if (people[l] + people[r] <= limit) l++; r--; ans++; } return ans; } }
- 时间复杂度：排序复杂度为 $O(n\log{n})$；双指针统计答案复杂度为 $O(n)$。整体复杂度为 $O(n\log{n})$
- 空间复杂度：$O(\log{n})$
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
也欢迎你 关注我（公主号后台回复「送书」即可参与看题解学算法送实体书长期活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 48983 | 91018 | 53.8% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
