救生艇

给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回 承载所有人所需的最小船数 。

示例 1：

1
2
3

输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)

示例 2：

1
2
3

输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)

示例 3：

1
2
3

输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)

我们初步进行思考，要找到船数最少的方案，那么每一艘船所承载的人都尽可能大，已知每一个人都不会超过船的承载范围，那么我们首先选一个重量最大的人，然后再选limit-people，新选择的人的质量是小于最大限度减去这个人的质量的所有人中的最大值，我们使用的是贪心策略。但是本题中有一个限制——每艘船最多承载两人，我们这种贪心的策略是解决这个问题方法的超集，我们应该进一步特殊化。如果每一次都进行最大最小值的查找，那么多次重复的查找无疑是一种可以优化的过程，我们将输入的数组排序，用双指针指向数组首尾两个元素，这样保证了每一次选择两个，同时判断左边和右边人的质量和和limit的大小，如果超了，说明最大质量的人只能一个和人乘一艘船，这时$p_1-=1$,如果没超，那么这两个人都上船，左右指针都移动一位

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def numRescueBoats(self,people:List[int],limit:int)->int:
        people.sort()
        p_0,p_1=0,len(people)-1
        numOfboat = 0
        while p_0 <= p_1:
            if people[p_0] + people[p_1] <= limit:
                p_0 += 1
                p_1 -= 1
                numOfboat += 1
            else:
                p_1 -= 1
                numOfboat += 1
        return numOfboat