Leetcode 881: Boats to Save People

Input: You are given an array of integers where each integer represents the weight of a person. You are also given a weight limit that each boat can carry.

Example: Input: people = [2, 3, 5, 8], limit = 8

Constraints:

• 1 <= people.length <= 5 * 10^4

• 1 <= people[i] <= limit <= 3 * 10^4

Output: You should return a single integer, which represents the minimum number of boats required to carry all the people.

Example: Output: 3

Constraints:

• The output is a single integer.

Goal: The goal is to minimize the number of boats used while ensuring that no boat carries more than its weight limit.

Steps:

• Sort the list of people by their weight.

• Use a two-pointer technique where one pointer starts at the lightest person and the other starts at the heaviest.

• If the combined weight of the two people is within the limit, they can share a boat.

• If not, the heavier person takes a boat alone.

• Continue this process until all people have been assigned to a boat.

Goal: The problem must be solved within the constraints of the problem size and time efficiency.

Steps:

• The solution must run efficiently for up to 50,000 people.

• The algorithm must handle large values for the weight limit (up to 30,000).

Assumptions:

• The input array contains weights of people that range between 1 and the boat's limit.

• There are no edge cases where a person weighs more than the boat's limit, as this will never be the case based on the constraints.

• Input: Input: people = [2, 3, 5, 8], limit = 8

• Explanation: The sorted people array is [2, 3, 5, 8]. The heaviest person (8) takes a boat alone, the next pair (2, 5) can share a boat, leaving 3 to take a boat on their own. Hence, 3 boats are needed.

• Input: Input: people = [4, 2, 6, 3], limit = 7

• Explanation: The sorted people array is [2, 3, 4, 6]. The pair (2, 6) shares a boat, and the pair (3, 4) shares a boat. Hence, 2 boats are needed.

Approach: The solution can be approached using a greedy strategy with a two-pointer technique. By sorting the array of people, we can try to pair the lightest and heaviest people to minimize the number of boats used.

Observations:

• The lightest and heaviest people should ideally share a boat if their combined weight is within the limit.

• By sorting the people by their weights and applying a two-pointer strategy, we can efficiently assign people to boats.

Steps:

• Sort the people array.

• Initialize two pointers: one at the beginning and the other at the end of the array.

• Check if the sum of the weights at the two pointers is less than or equal to the limit.

• If so, move both pointers inward and count the boat.

• If not, move only the pointer at the end inward, counting the boat for the person at the end.

• Repeat the process until all people are assigned to boats.

Empty Inputs:

• The problem constraints guarantee that there will be at least one person.

Large Inputs:

• Ensure that the solution can handle up to 50,000 people efficiently.

Special Values:

• When everyone is of the same weight, pairing them optimally will reduce the number of boats.

Constraints:

• The input size can be large, so an efficient solution using sorting and two-pointer strategy is required.

int numRescueBoats(vector<int>& people, int limit) {
    sort(people.begin(), people.end());
    int lo = 0, hi = people.size() - 1;
    int boats = 0;
    while(lo <= hi) {
        
        if(people[lo] + people[hi] <= limit) {
            lo += 1;
            hi -= 1;
        } else hi -= 1;
        
        boats++;
    }
    
    return boats;
}

1 : Function Definition

int numRescueBoats(vector<int>& people, int limit) {

This line defines the function `numRescueBoats` that accepts a vector of people and a limit for the boat's weight capacity.

2 : Sorting

    sort(people.begin(), people.end());

The list of people is sorted in non-decreasing order to facilitate pairing the heaviest and lightest people.

3 : Initialization

    int lo = 0, hi = people.size() - 1;

Two pointers `lo` and `hi` are initialized, where `lo` points to the lightest person, and `hi` points to the heaviest.

4 : Variable Setup

    int boats = 0;

A counter `boats` is initialized to track the number of boats needed.

5 : Loop Setup

    while(lo <= hi) {

The loop continues as long as the `lo` pointer is less than or equal to the `hi` pointer, meaning there are people still unpaired.

6 : Condition Check

        if(people[lo] + people[hi] <= limit) {

The condition checks if the lightest (`lo`) and heaviest (`hi`) person can be paired together in one boat without exceeding the weight limit.

7 : Pointer Adjustment

            lo += 1;

If they can be paired, the `lo` pointer is moved right to consider the next lightest person.

8 : Pointer Adjustment

            hi -= 1;

The `hi` pointer is moved left to consider the next heaviest person.

9 : Condition Check (Else)

        } else hi -= 1;

If the lightest and heaviest people can't fit together, only the heaviest person (pointed by `hi`) is placed in a boat.

10 : Boats Increment

        boats++;

Regardless of whether two people are paired or only one person is placed in the boat, the boat count is incremented.

11 : Return Statement

    return boats;

The function returns the total number of boats needed.

Best Case: O(n log n)

Average Case: O(n log n)

Worst Case: O(n log n)

Description: The time complexity is dominated by the sorting step, which is O(n log n), followed by a linear scan with two pointers.

Best Case: O(1)

Worst Case: O(n)

Description: The space complexity is O(n) due to the space required for sorting the array, though this could be O(1) if sorting in place.

Leetcode 881: Boats to Save People

Explore →