# # 【LeetCode】881. Boats to Save People 解题报告（Python）

## # 题目描述：

The i-th person has weight people[i], and each boat can carry a maximum weight of limit.

Each boat carries at most 2 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. (It is guaranteed each person can be carried by a boat.)

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)

Note:

1. 1 <= people.length <= 50000
2. 1 <= people[i] <= limit <= 30000

## # 解题方法

1. 如果两个人能坐在同一条船上，那么把两个指针向中间移动
2. 如果两个人的重量大于船的载重，那么让胖的人坐！因为瘦的人可以和别人挤挤，但是胖子不行啊，这个船必须都是他的了。（汽车的副驾驶2333）
3. 重复上述操作

class Solution(object):
def numRescueBoats(self, people, limit):
"""
:type people: List[int]
:type limit: int
:rtype: int
"""
people.sort()
res = 0
hi, lo = len(people) - 1, 0
while hi >= lo:
if people[hi] + people[lo] <= limit:
lo += 1
hi -= 1
res += 1
return res

https://leetcode.com/problems/boats-to-save-people/discuss/156855/6-lines-Java-O(nlogn)-code-sorting-+-greedy-with-greedy-algorithm-proof.

## # 日期

2018 年 9 月 21 日 —— 转眼这个月又快过去了