881. Boats to Save People

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.

Example 1:

Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)

Example 2:

Input: people = [3,2,2,1], limit = 3
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)

Constraints:

• 1 <= people.length <= 5 * 104

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

Tags

Two Pointers, Greedy

Solution

Sort the given array and assign two pointers (due to the capacity) at both ends of it. If the sum of both people's weight makes the overload of a boat, meaning that only the heavier person can be loaded on the boat, we only move the right pointer towarding to center and increase the result by 1. Otherwise, we also move the left pointer because this person can also be fitted into the boat. When two pointers overlap with each other, we also add 1 onto the result.

Complexity

• Time complexity: $O(n\log(n))$, which depends on the sort algorithm;

• Space complexity: $O(\log(n))$, which depends on the sort algorithm.

Code

func numRescueBoats(people []int, limit int) int {
	ans, l, r := 0, 0, len(people)-1
	sort.Ints(people)
	for l <= r {
		if people[l]+people[r] <= limit {
			l++
		}
		r--
		ans++
	}
	return ans
}