发表于 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

• LC 题目链接