Boats to save people

Each boat carries at most two people with a combined weight up to the limit. Sort, then always send the heaviest person, taking the lightest along whenever they fit.

The idea

The heaviest person needs a boat no matter what. The best partner to give them is the lightest person: if even the lightest does not fit, nobody does, so the heaviest goes alone. If the lightest fits, pairing them can never hurt, because anyone else could swap into that seat only by being heavier. Repeat with the two pointers moving inward.

Code

public int NumRescueBoats(int[] people, int limit) {
    Array.Sort(people);
    int l = 0, r = people.Length - 1, boats = 0;
    while (l <= r) {
        if (people[l] + people[r] <= limit) l++; // lightest fits with the heaviest
        r--; // the heaviest leaves on this boat either way
        boats++;
    }
    return boats;
}

Tips

• Every weight is at most the limit, so the heaviest person can always go alone.
• Pairing the heaviest with the lightest is the greedy choice; pairing two light people first can waste a boat. Try 1, 2, 2, 3 with limit 3: greedy needs 3 boats.
• When l and r meet, one person is left and takes the last boat alone.

In the .NET library

Array.Sort on an int[] is an in-place introsort, O(n log n). It modifies the caller's array; copy it first (people.ToArray()) if that matters.