LeetCode 881: Boats to Save People

Description

You are given an array people where people[i] is the weight of the ith person, and an infinite number of boats where each 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.

Constraints

• 1 <= people.length <= 5 * 104
• 1 <= people[i] <= limit <= 3 * 104

Examples

• Example 1:
  Input: people = [1,2], limit = 3
Output: 1
  Explanation: 1 boat (1, 2)
• Example 2:
  Input: people = [3,2,2,1], limit = 3n = 1, bad = 1
Output: 3
  Explanation: 3 boats (1, 2), (2) and (3)
• Example 3:
  Input: people = [3,5,3,4], limit = 5
Output: 4
  Explanation: 4 boats (3), (3), (4), (5)

Solution 1: Sorting + Two Pointers

Thought

According to the question, each boat can carry a maximum of two people. Therefore, the best scenario is to arrange two passengers, one heavy and one light, on the same boat. This way, we can minimize the total number of boats required. We can achieve this by sorting the input array and using a two-pointer approach.

Steps

1. Initialize the variable boats_number to keep track of the current total number of boats required.
2. Initialize two pointers, i and j, and start moving them from the beginning and end of the people array, respectively.
3. Sort the people array in ascending order.
4. When the i pointer is less than or equal to the j pointer, try to place the two people at positions i and j onto the boat:
   1. If the total weight of the two people (people[i] + people[j]) is less than or equal to the limit, it means we can take both of them on the same boat. Move the i pointer to the right and also move the j pointer to the left.
   2. If the total weight of the two people is greater than the limit, it means that the current boat can only carry the person with the greater weight (people[j]). Move the j pointer to the left.
   3. Increase the boats_number by 1.
5. Finally, return the value of boats_number.

Codes

def num_rescue_boats(people: List[int], limit: int) -> int:
    boats_number = 0
    i = 0
    j = len(people) - 1

    people.sort()

    while i <= j:
        if people[i] + people[j] <= limit:
            i += 1
            j -= 1
        else:
            j -= 1
		boats_number += 1

    return boats_number

Complexities

• Time Complexity: O(NlogN),  where N is the length of the people array.
• Space Complexity: O(1)

References

• LeetCode link: Boats to Save People – LeetCode