public int numRescueBoats(int[] people, int limit) {
if (people == null || people.length == 0 || limit <= 0) {
return 0;
}
Arrays.sort(people);
int start = 0;
int end = people.length;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (canSaveWith(mid, people, limit)) {
end = mid;
} else {
start = mid;
}
}
if (canSaveWith(start, people, limit)) {
return start;
} else {
return end;
}
}
private boolean canSaveWith(int boatCnt, int[] people, int limit) {
int i = 0;
int j = people.length - 1;
while (i <= j && boatCnt > 0) {
if (people[i] + people[j] > limit) {
j--;
} else {
j--;
i++;
}
boatCnt--;
}
return i > j;
}
贴一个solution的贪心,感觉很像...
public int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int i = 0, j = people.length - 1;
int ans = 0;
while (i <= j) {
ans++;
if (people[i] + people[j] <= limit)
i++;
j--;
}
return ans;
}