第 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

 

思路：

贪心策略  先升序排序  用每次最小的数  看能不能找到一个最大的数合坐一条船（所有找不到的不能合坐的 全部单独坐一条船）

public int numRescueBoats(int[] people, int limit) {
		if (people == null || people.length == 0) {
			return 0;
		}
		Arrays.sort(people);
		int res = 0;
		int left=0;
		int right=people.length-1;
		//左指针在前进的时候  从右边找到第一个能和最小的数合坐一条船的数   该数右边的数全部单独坐一条船
		while (left<=right) {
			if (people[left]<=limit) {
				while  (left<right&&people[left]+people[right]>limit) {    //从右边找到所有不能合坐的  单独坐一条船
					res++;           //结果+1
					right--;         //右指针减小
				}
				//第一个可以合坐一条船的
				right--;
			}
			res++;
			left++;		
		}
		return res;
	}