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 <vector>
2#include <algorithm>
3#include <iostream>
4
5int numRescueBoats(std::vector<int>& people, int limit) {
6 std::sort(people.begin(), people.end());
7 int i = 0, j = people.size() - 1;
8 int boats = 0;
9 while (i <= j) {
10 if (people[i] + people[j] <= limit) i++;
11 j--;
12 boats++;
13 }
14 return boats;
15}
16
17int main() {
18 std::vector<int> people = {3, 2, 2, 1};
19 int limit = 3;
20 std::cout << numRescueBoats(people, limit) << std::endl;
21 return 0;
22}This solution sorts the people vector and uses two pointers similar to the C version. It tries to pair the lightest and heaviest person, ensuring we always use the least number of boats necessary by exploring optimal pairings.
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.
1using System;
2
public class RescueBoatsGreedy {
public int NumRescueBoats(int[] people, int limit) {
Array.Sort(people);
int i = 0, j = people.Length - 1;
int boats = 0;
while (i <= j) {
if (people[i] + people[j] <= limit) {
i++;
}
j--;
boats++;
}
return boats;
}
public static void Main() {
int[] people = {3, 5, 3, 4};
int limit = 5;
RescueBoatsGreedy rb = new RescueBoatsGreedy();
Console.WriteLine(rb.NumRescueBoats(people, limit));
}
}Through an organized sort approach and efficient weight management, this technique disseminates the heaviest persons solo when necessary, focusing on solution integrity and minimal vessel usage.