409. Minimum Boats Required to rescue people

Objective: Given N people need to be rescued by crossing the river by boat. Each boat can carry a maximum weight of given limit K. Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most limit K.

Write an algorithm to find the minimum number of boats required for N people to cross the river.

Example:

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

Input: people = [5, 1, 4, 2], limit = 6
Output: 2
Explanation: 
2 boats 
First boat with people -(1, 5)
Second boat with people - (4, 2)

Input: people = [3, 4, 1, 2], limit = 4
Output: 3
Explanation: 
3 boats
First boat with people - (1, 3)
Second boat with people - (4)
Third boat with people - (2)

Approach:

1. Sort the array in ascending order. 
2. Take two pointers, left pointer at the beginning of the array and right pointer at the most of array. Check persons at the left pointer and right pointer and add their weights
   1. If the sum of weights is <= limit K then both persons can be in one boat. increment left pointer and decrement right pointer. add 1 to the total number of boats required.
   2. else person at the right pointer has to go in one boat so decrement right pointer. add 1 to the total number of boats required.

Time Complexity: O(nlogn)

Output:

 Total Number of boats required: 3

Source: Leetcode