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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 return (*(int*)a - *(int*)b);
6}
7
8int numRescueBoats(int* people, int peopleSize, int limit) {
9 qsort(people, peopleSize, sizeof(int), compare);
10 int i = 0, j = peopleSize - 1;
11 int boats = 0;
12 while (i <= j) {
13 if (people[i] + people[j] <= limit) i++;
14 j--;
15 boats++;
16 }
17 return boats;
18}
19
20int main() {
21 int people[] = {3, 2, 2, 1};
22 int limit = 3;
23 printf("%d\n", numRescueBoats(people, 4, limit));
24 return 0;
25}Here, we first sort the array of people's weights. Then, using two pointers (one at the start and one at the end), we check if the lightest person (start) and the heaviest person (end) can share a boat. If they can, we move both pointers inward. If not, we move only the end pointer. We increment the boat count in each iteration. This ensures each person is considered.
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.
1#include <iostream>
2#include <vector>
#include <algorithm>
int numRescueBoats(std::vector<int>& people, int limit) {
std::sort(people.begin(), people.end());
int i = 0, j = people.size() - 1;
int boats = 0;
while (i <= j) {
if (people[i] + people[j] <= limit) {
i++;
}
j--;
boats++;
}
return boats;
}
int main() {
std::vector<int> people = {3, 5, 3, 4};
int limit = 5;
std::cout << numRescueBoats(people, limit) << std::endl;
return 0;
}With a focus on efficiency, the solution uses C++'s sort and pairs most efficiently using two pointers until all individuals have been assigned to boats, aiming for optimal resource use.