Given an integer array people where people[i] represents the weight of the i th person and also given an integer limit representing the maximum weight capacity of a single boat.
Each boat can carry a maximum of exactly two people at the same time, provided that the sum of the weights of those two people does not exceed the limit. Return the minimum number of boats required to carry every single person.
Example 1
Input: people = [1, 2], limit = 3
Output: 1
Explanation: Both people can sit in one boat because 1 + 2 = 3.
Example 2
Input: people = [3, 2, 2, 1], limit = 3
Output: 3
Explanation: One valid arrangement is [1, 2], [2], and [3].
Brute Force Approach
The intuition behind this approach is to form valid boat pairs directly.
For a person who still needs a boat, the best possible use of that boat is to pair them with the heaviest available person who can still fit within limit.
A heavier valid partner is preferred over a lighter valid partner because it removes a more difficult person from future boat decisions.
If no valid partner exists, that person has to go alone. This idea is simple, but it becomes slow because the best partner is found by checking possibilities directly.
Algorithm
Maintain a
rescuedmarker so a person already assigned to a boat is not processed again.Visit the array from left to right; if the current person is already rescued, skip that position.
For every unrescued current person, assign one new boat and mark that person as rescued.
Search only the later indices for an unrescued partner whose weight can fit with the current person.
Keep the heaviest valid partner found during that search, then mark that partner as rescued if one exists.
Finish after the last index is processed, and return the total number of boats.Return the total
boats.
Dry Run
boats to save people
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the minimum number of boats needed. int numRescueBoats(vector<int>& people, int limit) { int n = people.size(); vector<bool> rescued(n, false); int boats = 0; // Try to assign a boat starting from each original index. for (int i = 0; i < n; i++) { // This person already shared an earlier boat, so no new boat is needed. if (rescued[i]) { continue; } boats++; rescued[i] = true; int bestPartnerIndex = -1; int maxValidWeight = -1; // Search later positions for the heaviest partner who can share this boat. for (int j = i + 1; j < n; j++) { // This later person is still waiting and fits with the current person. if (!rescued[j] && people[i] + people[j] <= limit) { // This valid partner is heavier than the best partner found so far. if (people[j] > maxValidWeight) { maxValidWeight = people[j]; bestPartnerIndex = j; } } } // A valid partner was found for the current boat. if (bestPartnerIndex != -1) { rescued[bestPartnerIndex] = true; } } return boats; }};// Driver codeint main() { vector<int> people = {3, 5, 3, 4, 2, 4, 1}; int limit = 6; // instance for class Solution Solution sol; cout << sol.numRescueBoats(people, limit) << endl; return 0;}Complexity Analysis
Time Complexity: `O(N²)`. We use nested loops, meaning for every unrescued person, we scan the entire remaining array to find the best possible partner.
Space Complexity: O(N). We allocate an additional boolean array of size N to keep track of who has been assigned a boat.
Optimal Approach
The most important observation is this: The heaviest remaining person is the hardest person to place.
So instead of randomly pairing people, handle the heaviest person first. Once the heaviest person is considered, there are only two useful choices: either pair them with the lightest remaining person, or send them alone.
The lightest person is considered because if the heaviest person cannot fit with the lightest person, then they cannot fit with anyone else either. Everyone else is heavier than or equal to the lightest person.
So the decision becomes very clean:
If the lightest and heaviest people fit together, put them in one boat.
Otherwise, the heaviest person must go alone.
This is greedy because each step makes the best safe decision for the heaviest remaining person.
Algorithm
Sort the
peoplearray in increasing order. This is done so the lightest person is at the left side and the heaviest person is at the right side.Keep two pointers:
leftat the lightest remaining person andrightat the heaviest remaining person. These pointers help check the best possible pair quickly.For every boat, always place the heaviest remaining person. This is important because that person has the least flexibility.
If the lightest and heaviest people can fit together, move both pointers. This means both people have been placed in the same boat.
Otherwise, move only the
rightpointer. This means the heaviest person goes alone because even the lightest person cannot fit with them.Increase the boat count after each step because one boat is used in every iteration.
Dry Run
boats to save people
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the minimum number of boats needed to carry all people within the weight limit. */ int numRescueBoats(vector<int>& people, int limit) { sort(people.begin(), people.end()); // left points to the lightest remaining person. int left = 0; // right points to the heaviest remaining person. int right = people.size() - 1; // boats stores how many boats have been used. int boats = 0; while (left <= right) { // If the lightest and heaviest can sit together, // both people are placed in the same boat. if (people[left] + people[right] <= limit) { left++; right--; } else { // If they cannot sit together, the heaviest // person must go alone in this boat. right--; } // One boat is used in both cases. boats++; } return boats; }};/* Runs a hard-coded example for quick testing.*/int main() { // Driver code starts vector<int> people = {3, 2, 2, 1}; int limit = 3; Solution obj; cout << obj.numRescueBoats(people, limit); return 0;}Complexity Analysis
Time Complexity: O(N log N) because sorting the array takes O(N log N), and the two-pointer scan takes O(n).
Space Complexity: O(1) extra space if sorting is considered in-place. Some languages may use extra internal space for their built-in sorting.
Interview follow-up Questions
The strict maximum of two people is a deliberate constraint of the problem to make the greedy logic work flawlessly. If a boat could hold three or more people, the simple "heaviest + lightest" two-pointer strategy would fail, and the problem would instantly become a highly complex bin-packing problem requiring advanced dynamic programming.
Be the first to add a comment.