Last Updated on 2022-03-24 by Clay
題目
You are given an array people where people[i] is the weight of the ith person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two 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.
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 * 1041 <= people[i] <= limit <= 3 * 104
我們會得到一串代表每個人體重的列表 people、以及一艘船最大的負重限制 limit。一艘船最多可以載兩人。
我們要返回的就是載完所有人所需的最少小船數量。
解題思路
Greedy（two pointers）解法
首先先將列表的體重進行排序，接著從兩端點開始匹配是否能兩人共乘一艘小船（當前最重跟最輕的組合）：
- 如果兩人相加在船的負重內，則讓兩人共乘，左右端點分別朝列表內部逼近
- 如果兩人相加超出船的負重，則讓重的人優先搭乘，僅右端點（假設重量從小排到大）減一。
每個判斷步驟後，都要把紀錄的所需小船數加一。
Greedy（two pointers）複雜度
由於需要替重量列表進行排序，故時間複雜度為 O(nlog(n))。不過除了紀錄左右端點位置、小船數量外沒有其餘空間開銷，故空間複雜度僅有 O(1)。
| Time complexity | O(nlog(n)) |
| Space complexity | O(1) |
Greedy （two pointers）解法 C++ 範例程式碼
class Solution {
public:
int numRescueBoats(vector<int>& people, int limit) {
// Init
int boats = 0;
int l = 0;
int r = people.size() - 1;
// Sort
sort(people.begin(), people.end());
// Two pointer
while (l <= r) {
if (people[l] + people[r] <= limit) {
++l;
--r;
}
else {
--r;
}
// Increase number of boats
++boats;
}
return boats;
}
};Greedy （two pointers）解法 Python 範例程式碼
class Solution:
def numRescueBoats(self, people: List[int], limit: int) -> int:
# Init
boats = 0
l = 0
r = len(people) - 1
# Sort
people.sort()
# Two pointer
while l <= r:
if people[l] + people[r] <= limit:
l += 1
r -= 1
else:
r -= 1
# Increase the number of boats
boats += 1
return boats