Boats to Save People

Dec 18, 2024 • 3 mins read

Problem Overview

The problem titled Boats to Save People falls under the greedy algorithm category on LeetCode. This problem requires us to determine the minimum number of boats needed to rescue a group of people. Each boat can carry a maximum weight limit, and each person has an associated weight. The goal is to use the fewest number of boats where each boat can carry at most two people at a time.

Understanding the Problem

Given an array people where people[i] is the weight of the i-th person, and an integer limit which represents the weight capacity of a boat, the task is to calculate how many boats are required to carry every person. It is important to note that a boat can carry at most two people simultaneously. The challenge is to optimize the usage of each boat by maximizing the total weight carried without exceeding the given limit.

Example

Let's consider an example for a clearer understanding:

Input: people = [3, 5, 3, 4], limit = 5
Output: 4
Explanation:
- Boat 1: [3, 3]
- Boat 2: [4]
- Boat 3: [5]

Key DSA Concepts and Theory

Greedy Algorithm

A greedy algorithm is an approach where decisions are made step-by-step, choosing the most optimal choice at each stage with the hope of finding a global optimum. The greedy choice is typically the best immediate choice and works well when the problem types permit this technique.

Two-pointer Technique

The two-pointer technique is a common pattern used for problems involving arrays or lists. It involves having two indices (or pointers) traverse the list/array, usually one starting from the beginning and one from the end, making decisions based on their combined conditions.

Solution Approach

The problem can be effectively solved using a greedy strategy combined with the two-pointer technique.

Step-by-step Solution

Sort the Array: Begin by sorting the people array. This enables efficient pairing of the lightest and heaviest people who can share a boat without exceeding the given limit.
Initialize Two Pointers: Use two pointers — low (starting at the beginning of the array) and high (starting at the end). These pointers help in pairing the heaviest and lightest individuals.
Pair People with Two Pointers:
- If the lightest (people[low]) and the heaviest (people[high]) combined do not exceed the limit, pair them and move both pointers inward (low++, high--).
- If they exceed the limit, place only the heaviest individual (people[high]) in a boat and move the high pointer inward (high--).
Count Boats: Each pairing or single allocation uses one boat. Consequently, increment a boats counter on each decision.

Code Implementation

Below are implementations in both C++ and Java:

C++ Code

#include <vector>
#include <algorithm>

class Solution {
public:
    int numRescueBoats(std::vector<int>& people, int limit) {
        std::sort(people.begin(), people.end());
        int low = 0, high = people.size() - 1;
        int boats = 0;

        while (low <= high) {
            if (people[low] + people[high] <= limit) {
                low++;
            }
            high--;
            boats++;
        }
        
        return boats;
    }
};

Java Code

import java.util.Arrays;

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int low = 0, high = people.length - 1;
        int boats = 0;

        while (low <= high) {
            if (people[low] + people[high] <= limit) {
                low++;
            }
            high--;
            boats++;
        }

        return boats;
    }
}

Time and Space Complexity Analysis

Time Complexity: O(n log n) due to the sorting step, where n is the number of people. The while loop operates with a linear complexity O(n).
Space Complexity: O(1), as no additional space proportional to input size is used apart from constant space for variables.

Common Mistakes to Avoid

Overlooking Sorting: Failing to sort the array initially can lead to inefficient or infeasible pairing.
Mismanagement of Pointers: Ensure the two pointers do not cross boundaries, which might cause out-of-bound errors.