using System;

using System.Linq;

public class Program

{

 /*

    An imminent hurricane threatens the coastal town of Codeville. If at most two people can fit in a rescue boat, and the max weight for a given boat is k, 

    determine how many boats will be needed to save everyone. For example, given a population with weights [100 , 200, 150, 80] and a boat limit of 200, 

    the smallest number of boats required will be three.

 */

    public static void Main()

    {

        var people = new int[] {100, 200, 150, 80};

        var k = 200; //max weight

        Console.WriteLine(MinNumberOfBoats(new int[]{105},k)); //1

        Console.WriteLine(MinNumberOfBoats(new int[]{200,150,30},k)); //2

        Console.WriteLine(MinNumberOfBoats(new int[]{50,50,50,50,50,50,50},k)); //4

        Console.WriteLine(MinNumberOfBoats(people,k)); //3

        Console.WriteLine(MinNumberOfBoats(new int[]{150,200,150,30},k)); //3

        Console.WriteLine(MinNumberOfBoats(new int[]{205},k));//exception

    }

    public static int MinNumberOfBoats(int[] people, int maxWeight)

    {

        if(people.Max() > maxWeight)

            throw new InvalidOperationException("One or more people are too heavy for the boats, Find alternate means for them and try again");

        if(people.Length == 1)

            return 1;

        int min_boats = 0;

        var idx = 0;

        while(idx<people.Length)

        {

            //Find the highest combination of people 

            //without exceeding the limit for this indexes weight

            (int idx, int v) max = (idx,0);

            for (int i = idx+1; i < people.Length;i++)    

            {

                var w = people[i]+people[idx];

                if(w<=maxWeight && w>max.v)

                    max=(i,w);

            }

            min_boats++;

            if(idx+1>=people.Length)

                break;

            //move this match out of the way

            //by swapping it to the next index space

            var p = people[idx+1];

            people[idx+1] = people[max.idx];

            people[max.idx] = p;

​

            if(idx+2 == people.Length)

            {

                min_boats++;

                break;

            }

            //advance the index beyond the newly

            //swapped item

            idx+=2;

        }

        return min_boats;

    }

}