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