Boats to Save People

Share

Each boat carries at most 2 people with total weight <= limit. Find minimum number of boats.

Example 1
Input: people=[1,2], limit=3 → Output: 1. Both can share a boat.
Example 2
Input: people=[3,2,2,1], limit=3 → Output: 3. (1,2),(2),(3) need 3 boats.

Solution Approach

Sort people. Use two pointers: pair lightest with heaviest when possible.

  • Sort people array
  • Use left and right pointers
  • If people[left]+people[right]<=limit, pair them (left++)
  • Always move right pointer left (right--)
  • Count boats
Java
public int numRescueBoats(int[] people, int limit) {
    Arrays.sort(people);
    int left = 0, right = people.length - 1, boats = 0;
    while (left <= right) {
        if (people[left] + people[right] <= limit) left++;
        right--;
        boats++;
    }
    return boats;
}
  • Time Complexity: O(n log n)
  • Space Complexity: O(1)