Question

881. 救生艇

English Version

题目描述

给定数组

 people 。people[i]表示第 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 <= 5 * 104
• 1 <= people[i] <= limit <= 3 * 104

解法

方法一：贪心 + 双指针

排序后，使用双指针分别指向数组首尾，每次取两个指针指向的元素之和与 limit 比较，如果小于等于 limit，则两个指针同时向中间移动一位，否则只移动右指针。累加答案即可。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组 people 的长度。

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

class Solution {
  public int numRescueBoats(int[] people, int limit) {
    Arrays.sort(people);
    int ans = 0;
    for (int i = 0, j = people.length - 1; i <= j; --j) {
      if (people[i] + people[j] <= limit) {
        ++i;
      }
      ++ans;
    }
    return ans;
  }
}

class Solution {
public:
  int numRescueBoats(vector<int>& people, int limit) {
    sort(people.begin(), people.end());
    int ans = 0;
    for (int i = 0, j = people.size() - 1; i <= j; --j) {
      if (people[i] + people[j] <= limit) {
        ++i;
      }
      ++ans;
    }
    return ans;
  }
};

func numRescueBoats(people []int, limit int) int {
  sort.Ints(people)
  ans := 0
  for i, j := 0, len(people)-1; i <= j; j-- {
    if people[i]+people[j] <= limit {
      i++
    }
    ans++
  }
  return ans
}

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