Two Pointers: Minimum boats to save people

Problem Statement:

You are given a people array that will have weight of ith person.

You are given infinite boats,but each boat can carry “w” weight.

You need to return the minimum number of boats to carry all the people.

Example:

Input: people = [1, 2] w = 3

Output: 1

1 boat can carry both people of combined weight 3

Solution Explanation:

We will use 2 pointers technique to solve the problem.

Sort the array, take 2 pointers pointing at the starting and ending of the array.

Now calculate if the lightest person + heaviest person is less than the sum, then sit them together in the boat.

else, heaviest person will go alone, along the way increment the counter.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int solution(vector<int>& people, int weight) 
{
   
    sort(people.begin(),people.end());
    
    int i = 0;
    int j = people.size() - 1;
    int count = 0;
    
    while(i <= j)
    {   

        if(people[i] + people[j] <= weight)
        {
            ++i;
            --j;
        }

        else
            --j;
        
        ++count; 
    }
    
    return count;
    
}

int main()
{
    vector<int> people = { 1, 2 };
    int weight = 3;

    cout << solution(people, weight) << endl;
    return 0;
}

Output

1