JAVA程序设计:救生艇(LeetCode:881)

第 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();
    	
    }
}

 

上一篇:MATLAB匿名函数(Anonymous Function)和求最小值--好文转载


下一篇:881-图解经典的进程调度算法