881.救生艇

链接：881.救生艇
难度：Medium
标签：贪心、数组、双指针、排序
简介：返回载到每一个人所需的最小船数。

题解 1 - typescript

• 编辑时间：2021-08-26
• 执行用时：176ms
• 内存消耗：45.6MB
• 编程语言：typescript
• 解法介绍：贪心，双指针从两边向中间计算。

function numRescueBoats(people: number[], limit: number): number {
  people.sort((a, b) => a - b);
  let ans = 0;
  let l = 0;
  let r = people.length - 1;
  while (l <= r) {
    if (people[r] + people[l] <= limit) l++;
    r--;
    ans++;
  }
  return ans;
}

题解 2 - python

• 编辑时间：2024-06-10
• 执行用时：84ms
• 内存消耗：22.12MB
• 编程语言：python
• 解法介绍：贪心使每条船上尽可能多。

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