Boats to Save People Problem

Problem

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.

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 = 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)

Solution

We should pair the least heavy and most heavy person together, as we are allowed at max 2 people in boat. In terms of physics that may cause imbalance, but in terms of this problem it will not. Now, we can either use maxHeap and minHeap, but that takes extra space. So, better solution is sorting and 2 pointers.

Method 1 - Sorting and Two Pointer

Here is the video explanation:

Code

Java

public int numRescueBoats(int[] people, int limit) {
	Arrays.sort(people);

	int numBoats = 0;

	int i =0;
	int j = people.length - 1;
	while (i <= j){
		// can we carry heaviest and lightest person
		if(people[i] + people[j] <= limit){
			i++;
			j--;
		}else {
			j--;
		}
		numBoats++;
	}
	return numBoats;
}