Number of Boats to Save People

Problem: Given an array 'weight', where weight[i] represents the weight of ith person and a 'limit' which represents the maximum weight each boat can carry. Suppose each boat can carry at most 2 people at the one 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. It is given that maximum of weight if less than or equal to limit.

Example:

Input: weight = [3,5,2,3], limit = 5
Output: 3
Explanation: 3 boats (3), (3, 2), (5)

Approach: The approach is simple which is Greedy. We can sort the given weight array. Now we will have the heaviest person at the end of array, the lightest person at the start of the array. 

The core logic is that if  heaviest person can't share a boat with the lightest person, then he can't pair with anyone, so he will get his own boat.

Now we can have two pointers approach here; one at the beginning and one at the end. We will move the pointers based on:

weight[start] + weight[end] <= limit

So our algorithm will look like following:

• start = 0, end = n - 1, requiredBoats = 0
• Sort(weight)
• WHILE start <= end
• IF weight[start] + weight[end] <= limit
• start = start + 1
• end = end - 1
• requiredBoats = requiredBoats + 1
• ELSE
• end = end - 1
• requiredBoats = requiredBoats + 1
• RETURN requiredBoats 

That's all.

Implementation in C#:

        public static int NumRescueBoats(int[] weight, int limit)

        {

            if (weight?.Length <= 1)

            {

                return (int)weight?.Length;

            }

            Array.Sort(weight);

            int numOfBoatsReq = 0;

            int i = 0, j = weight.Length - 1;

            while(i <= j)

            {

                if (weight[i] + weight[j] <= limit)

                {

                    ++i;

                    --j;

                    ++numOfBoatsReq;

                }

                else

                {

                    --j;

                    ++numOfBoatsReq;

                }

            }

            return numOfBoatsReq;

        }

Complexity: O(nlogn)