Arrays - Boats to Save People

You are given an array people where people[i] is the weight of the i^th 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.

Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat can carry both (1, 2) since the limit is 3.

Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3).

Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5).

Constraints:

1 <= people.length <= 5 * 10⁴
1 <= people[i] <= limit <= 3 * 10⁴

Solution 1 - Sort input array, then place people into boats with mix of higher and lower weights

The main intution behind this solution is, since we have people with mix of weights in the array, inorder to ulitize minimum number of boats, we first have fit maximum weight people and if there is still room, then fit low weight people with a maximum of two people and total weight is less than or equal to limit, let's look at below example:

Say if people = [3, 2, 4, 1] and limit = 4, if we look at one by one:

First, we can place 3 into one boat, because the next element is 2, but the limit is 4.
Next, we will place 2 into next boat.
Then, 4 in another boat
Next, 1 in a separate boat.

If we place people like this into boats, we need 4 boats, but as you can see person with weight 1, can be placed in 1^st boat along with 3, or it can be placed in 2^nd boat along with 2, because both have room for weight 1. So an optimal solution would be (3,1), (2), (4) or (3), (2, 1), (4), so we can minimize number of boats to only 3.

So, in this approach we will sort the input array first, then mix people with higher weights and lower weights if there is room. Let's apply the solution above problem.

After sorting the array it will become [1,2,3,4]
First, we will take the highest weight from right side, which is 4, we will put this person into 1^st boat, since there is no room after placing this person, we cannot add any smaller weight people.
Then, take the next highest weight from right side, which is 3, place this person into 2^nd boat, since there is still room for weight 1, check the lowest weight from left side, which is 1, this can fit into the same boat, so the second boat will carry (3, 1) weights.
Remaining weight is 2, we wil place this into a separate boat.
So, total minimum number of boats required are 3.

import java.util.Arrays; public class BoatsToSavePeople { static int numRescueBoats(int[] people, int limit) { Arrays.sort(people); int result = 0; int l = 0; int r = people.length - 1; while (l <= r) { int remain = limit - people[r--]; result += 1; if (remain >= people[l]) { l++; } } return result; } public static void main(String[] args) { System.out.println(numRescueBoats(new int[]{3, 4, 1, 2}, 4)); System.out.println(numRescueBoats(new int[]{3, 2, 2, 1}, 3)); System.out.println(numRescueBoats(new int[]{3, 5, 3, 4}, 5)); } }

Complexity Analysis:

Time complexity: Above code runs in O(n log n) time where n is the length of people array, since we are sorting the input array.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Complexity Analysis: