第 i 个人的体重为 people[i],每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人,但条件是这些人的重量之和最多为 limit。
返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
示例 1:
输入:people = [1,2], limit = 3
输出:1
解释:1 艘船载 (1, 2)
示例 2:
输入:people = [3,2,2,1], limit = 3
输出:3
解释:3 艘船分别载 (1, 2), (2) 和 (3)
示例 3:
输入:people = [3,5,3,4], limit = 5
输出:4
解释:4 艘船分别载 (3), (3), (4), (5)
提示:
1 <= people.length <= 50000
1 <= people[i] <= limit <= 30000
思路:我们考虑从体重最大的人开始装船,为了尽可能的少用船,我们一定是让每艘船多出来的空间尽可能的小,也就是说对于当前体重的人来说,我们一定是找一个和他体重加在一起总体重不超过limit的尽可能重的人装在一起。
首先对数组进行排序(因为我们要从最重的人开始遍历),然后维护一个优先队列表示当前有些船已经有人了(还差一个人),这个优先队列一定是升序的队列(读者可以自己思考下为什么不能降序?),每次若队头和当前要装船的人体重总和不超过limit,则将该人和队头的人一起装船。否则另开新船。
class Solution {
public int numRescueBoats(int[] people, int limit) {
int n=people.length,ans=0;
PriorityQueue<Integer> q=new PriorityQueue<>();
Arrays.parallelSort(people);
for(int i=n-1;i>=0;i--) {
if(!q.isEmpty() && people[i]+q.peek()<=limit) {
q.poll();
ans++;
}
else
q.add(people[i]);
}
return ans+q.size();
}
}