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:

1. Sort the people array by their weight in ascending order.
2. Initialize two pointers, start and end to first and last indices of the people array respectively.
3. Initialize variable boats to zero.
4. Move both pointers towards each other until start <= end.
5. 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.–
6. 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.
7. 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;
}