[Leetcode][881. Boats to Save People] Greedy: Let the Heaviest match the lightest, if not matched, let it alone

By Long Luo

This article is the solution of Problem 881. boats to save people.

Greedy

We should let the Heaviest person match the lightest person and create the most pairs whose weight didn’t exceed the limit, and so on.

If not, let the heavy person occupy a whole boat.

I write the brute force code first.

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
public int numRescueBoats(int[] people, int limit) {
int len = people.length;
Arrays.sort(people);
int ans = 0;
int idx = 0;
int right = len - 1;
while (idx < len) {
while (idx < len && people[idx] == 0) {
idx++;
}

while (right > idx && people[right] > 0 && people[idx] + people[right] > limit) {
right--;
}

if (right > idx && people[idx] + people[right] <= limit) {
people[idx] = 0;
people[right] = 0;
idx++;
right--;
ans++;
} else if (idx < len) {
people[idx] = 0;
idx++;
ans++;
}
}

return ans;
}

It was ugly, then I wrote such code below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 public int numRescueBoats(int[] people, int limit) {
int len = people.length;
Arrays.sort(people);
int left = 0;
int right = len - 1;
int ans = 0;
while (left <= right) {
if (people[left] + people[right] <= limit) {
left++;
right--;
ans++;
} else {
right--;
ans++;
}
}

return ans;
}

Analysis

  • Time Complexity: O(nlogn)O(nlogn)
  • Space Complexity: O(logn)O(logn)

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗