### 题目

The i-th person has weight people[i], and each boat can carry a maximum weight of limit.

Each boat carries at most 2 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. (It is guaranteed each person can be carried by a boat.)

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)


Note:

• 1 <= people.length <= 50000
• 1 <= people[i] <= limit <= 30000

### 先排序，然后贪心算法，复杂度O(n^2)

limit = 5

|
[5,4,4,3,3,2,1]


limit = 5
-第二条船-
|  ->     |
[5,4,4,3,3,2,1]


#### 代码

public int numRescueBoats(int[] people, int limit) {
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < people.length; i++) {
}
list.sort(new Comparator<Integer>(){
public int compare(Integer a, Integer b) {
return b - a;
}
});

int numBoats = 0;
while (!list.isEmpty()) {
int remain = limit - list.remove(0);
for (int i = 0; remain > 0 && i <list.size(); i++) {
if (list.get(i) <= remain) {
remain -= list.remove(i); break;
}
}
numBoats++;
}
return numBoats;
}


### 非贪心的”Two Pointers”，复杂度O(n)

5先走
|           |
[5,3,3,3,3,2,1]


5这个乘客太重，无法再搭载1

    3和1一起走
|         |
[5,3,3,3,3,2,1]


31一起走。我们不需要担心浪费的情况，不需要强迫3带2，因为，

• 只要后面还有乘客，他的体重一定小于3，肯定能带走2
• 如果后面除了2没有其他乘客，那就算3带走2，剩下的1还是要单独一条船带走，所以强制3带走2并不节省船只

#### 代码

class Solution {
public int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int numBoats = 0;
for (int i = people.length - 1, j = 0; i >= 0 && i >= j; i--) {
if (i > j && people[i] + people[j] <= limit) {
j++;
}
numBoats++;
}
return numBoats;
}
}