rescueboat.txt

rescueboat.txt

Boat to save people.
	 
We're trying to add people in safety boats.

We're given an array of people and an integer limit.
People array is an array of people's weights, so the "i-th" person weights a person at position "i" and each boat can carry at most
the number of limit.

Each boat carries at most 2 people at the same time, given that their weight sum is at most the limit.
Our task is just to return the minimum number of boats to carry a given person.

Note:
1. The maximum number of people a boat can carry is 2
2. Every person has a weight lower or equal to the limit.
3. worst-case scenario is that it would take as many boats as there are people.

Example:
people = [1,2]
limit = 3

question: what is the number of boats to carry each person?
ans: 1

how:
one boat carries 1st and 2nd person because the sum of the array is equal to limit and they're just 
two items in the array.


We'll want to maximize the number of pairs of people whose weight can be added together in the same boat.
(sum of their weights is lower or equal to the limit).


Steps:
1. sort the array
2. attempt to add the heaviest person and the lightest person in the same boat.
 what we'll use to match the heaviest and lightest available people?
 we'll use the two-pointers technique.

 initialize 2 pointers, "left" at the beginning of the array and "right" at the end of the array, as well as initializing the boats_number
 to "0"

3. Loop as long as the right pointer is bigger than or equal to the left pointer.
 When the left and right pointers are equal, we'll increment the number of boats needed and break from the loop.
 That means, the only the person will enter the boat because the pointer is pointing at him as the heaviest or lightest person

 if the weights of people at the left and right pointer are lower or equal to the limit, we'll move the left pointer to the right and right pointer
 to left and increase the number of boats needed.

 if the weight of people at the left and right pointers is bigger than the left limit, move the right pointer to left, increment the number
 of boats needed.
 (add the highest in a boat by himself).

 Time Complexity: O(N log(N)).

 Space Complexity: 0(1)