Sponsored
Sponsored
This approach utilizes sorting and a two-pointer technique. By sorting the array, we simplify the pairing process, always trying to pair the lightest and heaviest person possible to fit within the limit. This method is greedy because it always tries to use the lightest and heaviest pair that fits to use fewer boats.
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) since we're sorting in place.
1function numRescueBoats(people, limit) {
2 people.sort((a, b) => a - b);
3 let i = 0, j = people.length - 1;
4 let boats = 0;
5 while (i <= j) {
6 if (people[i] + people[j] <= limit) i++;
7 j--;
8 boats++;
9 }
10 return boats;
11}
12
13const people = [3, 2, 2, 1];
14const limit = 3;
15console.log(numRescueBoats(people, limit));Using JavaScript's sort function, we first order the array. With two pointers, this algorithm calculates the minimum number of boats by pairing from the outermost to the center of the sorted array.
In this approach, we again sort the weights, but the main focus is on maximizing each boat's capacity. If the heaviest person cannot be paired with the lightest one, they solely occupy a boat.
Time Complexity: O(n log n) - Primary time usage is the sorting step. Space Complexity: O(1) when sorting in-place.
1import
Utilizing a greedy mechanism, Java's sorting and pointer steps ensure every person fits optimally into boats, recognizing when sole riding becomes necessary due to capacity limits.