[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 Greedy: Let the Heaviest Match the Lightest, if Not Matched, Let it Alone of Problem 881. boats to save people.
Intuition
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
30public 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(n \log n)\)
- Space Complexity: \(O(\log n)\)
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. 😉😃💗