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.

OR

An imminent hurricane threatens the coastal town of Codeville. If at most two people can fit in a rescue boat, and the maximum weight limit for a given boat is k, determine how many boats will be needed to save everyone.

For example, given a population with weights [100, 200, 150, 80] and a boat limit of 200, the smallest number of boats required will be three.

Examples

Example 1:

1
2
3

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

Example 2:

1
2
3

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

Example 3:

1
2
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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;
}