# 救生艇 - Boats To Save People

## 881. 救生艇 - Boats To Save People

[双指针] [桶排序]

``````第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。

``````

### Example:

``````输入：people = [1,2], limit = 3

``````
``````输入：people = [3,2,2,1], limit = 3

``````

## solution

### My solution >> 54ms [双指针 + 贪心算法 ]

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 `````` ``````class Solution { public int numRescueBoats(int[] people, int limit) { Arrays.sort(people); int answer = 0; int i = 0, j = people.length - 1; while(i <= j){ if(people[i] + people[j] <= limit) i++; j--; answer++; } return answer; } } ``````

### Other Solution >> 16ms [桶排序]

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 `````` ``````class Solution { //对于Limite很小的情况用桶排序 public int numRescueBoats(int[] people, int limit) { int[] busket = new int[limit + 1]; for(int i = 0; i < people.length; i++) busket[people[i]] += 1; int count = busket[limit]; // 先让所有只能一个人坐船的人离开 int start = 1; int end = limit - 1; //1号桶到倒数第二个桶 while(start <= end){ if(busket[start] <= 0){ start++; continue; } if(busket[end] <= 0){ end--; continue; } if(start + end == limit){ busket[start]--; busket[end]--; count++; continue; } if(start + end > limit){ busket[end]--; count++; continue; } if(start + end < limit){ busket[end]--; busket[start]--; count++; continue; } } return count; } } ``````