Greedy Algorithms with Two Pointers

Two pointers become a greedy algorithm when their movements encode safe irreversible decisions. We solve the minimum-boats problem: each person has a weight, a boat carries at most two people, and total weight cannot exceed a fixed capacity. Sorting lets us decide whether the lightest remaining person can accompany the heaviest. The two-person restriction is essential to the proof.

Prerequisites: Greedy exchange proofs; sorting; index ranges.

Build the idea

1. Define feasible pairings

   Every person must be assigned once, one boat can carry one or two people, and weights are nonnegative. A person heavier than capacity makes the instance impossible. Sort weights increasingly and maintain indices left and right for the unassigned range. The heaviest remaining person must leave now on some boat; the question is whether that boat can safely take a companion.

2. Make the pointer decision

   If lightest+heaviest exceeds capacity, no other companion is lighter, so the heaviest must travel alone. Otherwise pair those two. Decrement right in every iteration, increment left only when a distinct lightest person is paired, and count one boat. When left==right, one unpaired person remains and uses one boat without being counted twice.

   $$\mathrm{lightest}+\mathrm{heaviest}\le \mathrm{capacity}$$

3. Correctness proof: exchange companions

   When the lightest L fits with heaviest H, some optimum can pair them. If H is alone, move L onto its boat; this cannot increase boat count. If H has companion X and L is alone, replace X by L and let X use L’s boat. If L has companion Y, replace the two pairs (H,X),(L,Y) by (H,L),(X,Y). Since Y≤H, X+Y≤X+H≤capacity. Thus the exchange preserves feasibility and boat count; recurse on the remaining people.

4. Trace the sample

   Weights [7,2,3,9] with capacity 10 sort to [2,3,7,9]. Nine cannot pair with two, so it goes alone. Seven pairs with two. Three remains alone. The result is three boats. Both-pointer movement removes exactly the people assigned, and every branch has a proof: forced alone or safely exchanged pair.

5. Distinguish technique from theorem

   A sliding-window two-pointer algorithm may simply maintain a range invariant and need no greedy optimality argument. Here pointers implement an exchange-backed optimization. If boats may carry three or more people, this specific pairing exchange no longer proves optimality; general bin packing is much harder. Do not extend the code by repeatedly filling spare capacity and assume the same minimum guarantee.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
int main(){
    int n;
    long long capacity;
    std::cin>>n>>capacity;
    std::vector<long long>weight(n);
    bool possible=true;
    for(auto&x:weight){
        std::cin>>x;
        if(x>capacity){
            possible=false;
        }
    }
    if(!possible){
        std::cout<<"IMPOSSIBLE\n";
        return 0;
    }
    std::sort(weight.begin(),weight.end());
    int left=0,right=n-1,boats=0;
    while(left<=right){
        if(left<right&&weight[left]+weight[right]<=capacity){
            ++left;
        }
        --right;
        ++boats;
    } // Always assign the heaviest remaining person.
    std::cout<<boats<<'\n';
}

Complexity analysis

O(n log n) sorting, then O(n) pointer work because each person is removed once. O(n) weight storage and O(1) extra pairing state. Weight sums use long long even though individual weights fit int.

Example input and output

Read n (0..100000), capacity (0..10^9), then n weights in 0..10^9. Boats hold at most two people. Print minimum boats, or IMPOSSIBLE if an individual exceeds capacity.

Input

4 10
7 2 3 9

Output

3

The greedy assignments are [9], [7,2], [3]; no valid pairing can fit 9 with another person.

Practical applications

Use for bounded two-item pairing and matching problems with an ordered exchange property. General two pointers also solve scans and windows without greedy choices; recognize which correctness argument your problem actually needs.

Check your understanding

Why must the heaviest go alone when even the lightest cannot fit with it?

Put it into practice

Compare with exhaustive pair/singleton partitions for up to eight people.