https://leetcode.com/problems/boats-to-save-people
881. Boats to Save People
给定一阵列people 此阵列代表需要上船的人 people[i]代表此人的体重
你现在有无限艘船 船有承重上限limit 每艘船一次最多载两个人
请回传带回所有人所需的最少船只数
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)
Constraints:
1 <= people.length <= 5 * 104
1 <= people[i] <= limit <= 3 * 104
思路:
排序然后two pointer
Python Code:
class Solution:
def numRescueBoats(self, people: List[int], limit: int) -> int:
people.sort()
boats = 0
light = 0
heavy = len(people) - 1
while light <= heavy:
if people[light] + people[heavy] <= limit:
light += 1
heavy -= 1
boats += 1
return boats