JZX轻语：简
LeetCode 1542 - 救生艇
发表于2024年05月20日
可使用贪心算法解决：先将people按体重排序，对于还没上船的人群中，选择其中体重最大的人，如果加上当前体重最小的人还没有超出船的承载量，则两个一起乘坐；否则，只承载最重的那个人。如此往复，直至全部人上船。上述过程可以使用双指针维护状态：左指针维护还没上船的人中最轻的人，右指针则指向最重的人。
class Solution:
def numRescueBoats(self, people: List[int], limit: int) -> int:
people.sort()
l, r = 0, len(people) - 1
ans = 0
while l < r:
if people[l] + people[r] <= limit:
l += 1
r -= 1
ans += 1
if l == r:
ans += 1
return ans