Leetcode 885 Boats to Save People

发表于 |

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. 我感觉这道题该归为easy才对，每条船最多只能装两个人，那么只要能装两个人我就装
  2. 从重量最大的人开始分析，能不能和重量最小的人一起呢？能就一起不能就拉倒！为什么在这里贪心不会出错呢？
  3. 因为之后分析的人的重量都比这个人要小，也就不存在某个人不能和现在这个人一起反而能和比这个人轻的人一起的情况。

思路：

  1. 用一个双向队列，分别把最重最轻的人依次出队
  2. 如果目前最重的人和最轻的人加一起比Limit要小，就都pop出来，否则就只pop最重的人
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def numRescueBoats(self, people, limit):
        """
        :type people: List[int]
        :type limit: int
        :rtype: int
        """
        people.sort()
        Q = collections.deque(people)
        res = 0
        while Q:
            w = Q.pop()
            if Q and Q[0] <= limit - w:
                Q.popleft()
            res += 1
        return res