Solution For Boats To Save People
Problem Statement:
You are given an array people where people[i] = [weighti, limiti] and a boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.
Return the minimum number of boats to carry every given person.
Example 1:
Input: people = [[1,2],[3,2],[4,3]], limit = 5
Output: 3
Explanation: The boatused are [1,2], [3,2], and [4,3].
Example 2:
Input: people = [[3,5],[3,5],[4,3],[2,5]], limit = 5
Output: 4
Explanation: The boatused are [3,2], [3,2], [4,3], and [2,5].
Approach:
The solution to this problem can be done by using a two-pointer approach. We can start by sorting the array of people by their weight in ascending order. This is because we want to first take the lightest people in the boat.
Let’s initialize two pointers, start, and end to the first and last indices of the people array respectively. We then keep moving these pointers inward towards each other. We keep taking people in boas as long as their weight summation is less than or equal to the limit. We continue this until we exhaust all the people.
In the boat, we can take two people at the most and should be equal to or greater than the weight value of each people in the boat. i.e., lightweight can be linked with only the lightweight and heavy weight can be linked with a heavyweight.
For example: people =[1,3,2,2] -> light: 1,2,2 -> 4/limit = 2,1 boats used.
Algorithm:
- Sort the people array by their weight in ascending order.
- Initialize two pointers, start and end to first and last indices of the people array respectively.
- Initialize variable boats to zero.
- Move both pointers towards each other until start <= end.
- If the weight of people pointed by start and end pointers is greater than the limit, then we can only take the heavy one with us in a boat, and boats count increases, end.–
- Else, we keep the count of both the people in the boat and move both the start and end pointers by incrementing start and decrementing end.
- After iterating through the whole array, we return the count of boats
Pseudo Code:
python
def num_rescue_boats(people: List[int], limit: int) -> int:
# sort the people by their weights in ascending order.
people.sort()
# Initialize start and end pointers
start, end = 0, len(people) - 1
# Initialize number of boats to 0 and iterate over the people array.
boats = 0
while start <= end:
# If the weight greater than limit, move end pointer
if people[end] + people[start] > limit:
end -= 1
# Otherwise, increment start and decrement end pointers
else:
start += 1
end -= 1
# Increment boat on each iteration
boats += 1
# Return the boat count
return boats
Time Complexity: O(n*log(n)) – for sorting where n = number of people
Space Complexity: O(1) – as we are not storing any extra data.
Final Solution:
“`python
from typing import List
def num_rescue_boats(people: List[int], limit: int) -> int:
# sort the people by their weights in ascending order.
people.sort()
# Initialize start and end pointers
start, end = 0, len(people) – 1
# Initialize number of boats to 0 and iterate over the people array.
boats = 0
while start <= end:
# If the weight greater than limit, move end pointer
if people[end] + people[start] > limit:
end -= 1
# Otherwise, increment start and decrement end pointers
else:
start += 1
end -= 1
# Increment boat on each iteration
boats += 1
# Return the boat count
return boats
“`
Step by Step Implementation For Boats To Save People
class Solution { public int numRescueBoats(int[] people, int limit) { // sort the array in ascending order Arrays.sort(people); // two pointer approach // start from the beginning and the end of the array int i = 0, j = people.length - 1; // result variable to store the number of boats int result = 0; // while the two pointers don't meet while (i <= j) { // if the sum of the weights of the people at the two pointers is less than or equal to the limit if (people[i] + people[j] <= limit) { // increment the first pointer i++; } // regardless of the above condition, we always want to decrement the second pointer // because we want to put the heavier person in the boat first j--; // increment the number of boats result++; } return result; } }
def numRescueBoats(people, limit): people.sort() i, j = 0, len(people) - 1 num_boats = 0 while i <= j: if people[i] + people[j] <= limit: i += 1 j -= 1 num_boats += 1 return num_boats
var nums = [1,2,3,4,5]; var limit = 3; var boatsToSavePeople = function(people, limit) { people.sort((a, b) => a - b); let i = 0; let j = people.length - 1; let boats = 0; while (i <= j) { boats++; if (people[i] + people[j] <= limit) { i++; } j--; } return boats; };
The problem can be found here: https://leetcode.com/problems/boats-to-save-people/ One possible solution is as follows: int numRescueBoats(vector& people, int limit) { // Sort the people in descending order by weight sort(people.rbegin(), people.rend()); // Initialize our result variable int result = 0; // Initialize two pointers, one at the beginning and one at the end of the vector int start = 0, end = people.size() - 1; // While the two pointers have not met each other while (start <= end) { // If the weight of the person at the start pointer plus the weight of the person at the end pointer is less than or equal to the limit if (people[start] + people[end] <= limit) { // We can fit both people on one boat, so we increment the end pointer end--; } // Otherwise, we can only fit one person on the boat // In either case, we increment the result variable and the start pointer result++; start++; } // Return the result return result; }
/* The problem can be solved using a greedy algorithm. We can sort the people in descending order by their weight. Then, we can pair the heaviest person with the lightest person until we have paired all the people or there are no more people left to pair. */ public int NumRescueBoats(int[] people, int limit) { // Sort the people in descending order by weight Array.Sort(people, (a, b) => b - a); // Initialize the number of boats to 0 int numBoats = 0; // Initialize left and right pointers int left = 0; int right = people.Length - 1; // While there are people left to pair while (left <= right) { // If the weight of the people at the left and right pointers // does not exceed the limit if (people[left] + people[right] <= limit) { // Move the right pointer to the left by one right--; } // Move the left pointer to the right by one left++; // Increment the number of boats numBoats++; } return numBoats; }