881. Boats to Save People
Medium
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 * 104
1 <= people[i] <= limit <= 3 * 104
解題
Runtime: 83 ms, faster than 100%
Memory Usage: 7.5 MB, less than 55.32%
func numRescueBoats(people []int, limit int) int {
sort.Ints(people)
ans := 0
right, left := len(people) - 1, 0
weight := 0 // 重量
count := 0 // 船上人數
for right >= left {
// 重量剛好到達上限 / 不能再上船了 / 人數滿了 -> 換一艘船
if weight == limit || weight + people[left] > limit || count == 2{
ans++
weight = 0
count = 0
}
if weight + people[right] <= limit {
weight += people[right]
count++
right--
continue
} else {
if weight + people[left] <= limit {
weight += people[left]
count++
left++
}
}
}
return ans + 1 // 加上最後一艘船
}
Last updated