We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Boats to Save People

Number: 917

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Bloomberg, Meta, Microsoft, Deutsche Bank

Problem Description

Given an array of integers representing the weights of people and an integer limit for a boat, determine the minimum number of boats required to save everyone. Each boat can carry at most two people with a combined weight not exceeding the limit.

Key Insights

  • Sort the list of people's weights.
  • Use the two pointers technique: one pointer at the beginning (lightest) and one at the end (heaviest).
  • If the sum of the weights at both pointers is within the boat's limit, pair them and move both pointers.
  • Otherwise, assign the heavier person alone and move the pointer for the heaviest.
  • Continue until all people are accounted for.

Space and Time Complexity

Time Complexity: O(n log n) due to the sorting step. Space Complexity: O(1) additional space (ignoring the space taken by sorting, which may be O(log n) depending on the implementation).

Solution

The solution uses a greedy approach combined with the two pointers technique. After sorting the array, we initialize two pointers: one at the start (pointing to the lightest person) and one at the end (pointing to the heaviest person). In each iteration, we check if the combined weight of the persons at these pointers is within the limit. If so, we pair them in a single boat and move both pointers. Otherwise, the heavier person boards a boat alone, and we move the pointer for the heaviest person. This process repeats until all people have been allocated a boat. This approach ensures that we use the minimum number of boats.

Code Solutions

# Function to calculate the minimum number of boats needed
def numRescueBoats(people, limit):
    # Sort the list of people's weights
    people.sort()
    # Initialize two pointers; left points to the lightest, right to the heaviest
    left, right = 0, len(people) - 1
    boats = 0  # Count of boats used
    
    # Iterate until all persons are assigned to a boat
    while left <= right:
        # If the lightest and heaviest person can share a boat, do so
        if people[left] + people[right] <= limit:
            left += 1  # Move left pointer to the next lightest person
        # Always move the right pointer as the heaviest person occupies a boat now
        right -= 1
        boats += 1  # Increment boat count for each allocation
        
    return boats

# Example usage:
# people = [3,2,2,1], limit = 3
# print(numRescueBoats(people, limit))  # Expected output: 3
← Back to All Questions