CareerCup

Algorithm is to sort the array (ascending) and walk indexes toward the middle, comparing the sum of the values at the two indexes with the max weight of the canoes (150). If the summed weight is less than 150, increment boat counter and move both indexes closer to middle of array. If summed weight is higher than 150, only increment boat counter if heaver child is less than max weight, then only move higher index toward center (decrement). The reasoning here is that we'll try to pair the lighter child with the next heaviest child on the list, so we want to leave the low index pointer where it is and then go to the next iteration.

I tried a few test cases and it seems to be working as expected.

Complexity would be O(nlogn) due to the sort at the beginning.

private static int GetMaxBoats(List<int> arr)
        {
            arr.Sort();
            /*foreach (int n in arr)
            {
                Console.WriteLine(n);
            }*/

            int lowIndex = 0;
            int highIndex = arr.Count - 1;
            int boatCounter = 0;

            while(lowIndex < highIndex)
            {
                if(arr[lowIndex] + arr[highIndex] <= 150)
                {
                    //2 kids fit
                    boatCounter++;
                    lowIndex++;
                    highIndex--;
                }
                else
                {
                    
                    if(arr[highIndex] <= 150)
                    {
                        // only 1 kid fits, put the larger kid in the boat if he fits
                        boatCounter++;
                    }
                    // Else, larger kid is too heavy to go on boat.

                    // Either way, we've handled the heavier child
                    highIndex--;
                }

                // cover case where both pointers point to same child
                if(lowIndex == highIndex)
                {
                    if (arr[highIndex] <= 150)
                    {
                        boatCounter++;
                    }

                    break;
                }
            }

            return boatCounter;
        }

Just create an array of size 150 and loop through each person and increment the count in the array by 1. Skip the person if their weight is more than 150. Then, just pair the heaviest person with the lightest person.

O(n)

Here is a NLogN solution, first thing we sort the kids which will take O(nlogN), then we do as
2 sum problem but here we do not search for exact value, we search for any combination from R and L that is less than 150, and we count 1.

class Kid{
public:
	double weight;
	Kid(double w=0) :weight(w){}

	bool operator<(const Kid& k)const{
		return weight < k.weight;
	}
};

int minNumberOfCanoe(const vector<Kid>& kids){

	vector<Kid> sortedKids = kids;

	sort(sortedKids.begin(), sortedKids.end());

	int L = 0;
	int R = sortedKids.size() - 1;

	int canonCount = 0;

	while (L <= R){
		int wBig = sortedKids[R].weight;
		int wSmall = sortedKids[L].weight;

		if (wBig + wSmall <= 150){
			canonCount++;
			R--;
			L++;
		}
		else if (wBig <= 150){
			canonCount++;
			R--;
		}
	}

	return canonCount;
}

int getCanoes(int[] array){
			if(array == null){
					return -1; 
			}
			
			int left = 0; 
			int right = array.length -1; 
			int count = 0; 
			while(left < right){
				if(array[left] + array[right] > MAX_WEIGHT){
					right--;
				}else{
					left++;
					right--;
				}
				count++;
			}
			return count;

}

Algorithm is to sort the array (ascending) and walk indexes toward the middle, comparing the sum of the values at the two indexes with the max weight of the canoes (150). If the summed weight is less than 150, increment boat counter and move both indexes closer to middle of array. If summed weight is higher than 150, only increment boat counter if heaver child is less than max weight, then only move higher index toward center (decrement). The reasoning here is that we'll try to pair the lighter child with the next heaviest child on the list, so we want to leave the low index pointer where it is and then go to the next iteration.

I tried a few test cases and it seems to be working as expected.

Complexity would be O(nlogn) due to the sort at the beginning.

private static int GetMaxBoats(List<int> arr)
        {
            arr.Sort();
            /*foreach (int n in arr)
            {
                Console.WriteLine(n);
            }*/

            int lowIndex = 0;
            int highIndex = arr.Count - 1;
            int boatCounter = 0;

            while(lowIndex < highIndex)
            {
                if(arr[lowIndex] + arr[highIndex] <= 150)
                {
                    //2 kids fit
                    boatCounter++;
                    lowIndex++;
                    highIndex--;
                }
                else
                {
                    
                    if(arr[highIndex] <= 150)
                    {
                        // only 1 kid fits, put the larger kid in the boat if he fits
                        boatCounter++;
                    }
                    // Else, larger kid is too heavy to go on boat.

                    // Either way, we've handled the heavier child
                    highIndex--;
                }

                // cover case where both pointers point to same child
                if(lowIndex == highIndex)
                {
                    if (arr[highIndex] <= 150)
                    {
                        boatCounter++;
                    }

                    break;
                }
            }

            return boatCounter;
        }

Algorithm is to sort the array (ascending) and walk indexes toward the middle, comparing the sum of the values at the two indexes with the max weight of the canoes (150). If the summed weight is less than 150, increment boat counter and move both indexes closer to middle of array. If summed weight is higher than 150, only increment boat counter if heaver child is less than max weight, then only move higher index toward center (decrement). The reasoning here is that we'll try to pair the lighter child with the next heaviest child on the list, so we want to leave the low index pointer where it is and then go to the next iteration.

I tried a few test cases and it seems to be working as expected.

Complexity would be O(nlogn) due to the sort at the beginning.

private static int GetMaxBoats(List<int> arr)
        {
            arr.Sort();
            /*foreach (int n in arr)
            {
                Console.WriteLine(n);
            }*/

            int lowIndex = 0;
            int highIndex = arr.Count - 1;
            int boatCounter = 0;

            while(lowIndex < highIndex)
            {
                if(arr[lowIndex] + arr[highIndex] <= 150)
                {
                    //2 kids fit
                    boatCounter++;
                    lowIndex++;
                    highIndex--;
                }
                else
                {
                    
                    if(arr[highIndex] <= 150)
                    {
                        // only 1 kid fits, put the larger kid in the boat if he fits
                        boatCounter++;
                    }
                    // Else, larger kid is too heavy to go on boat.

                    // Either way, we've handled the heavier child
                    highIndex--;
                }

                // cover case where both pointers point to same child
                if(lowIndex == highIndex)
                {
                    if (arr[highIndex] <= 150)
                    {
                        boatCounter++;
                    }

                    break;
                }
            }

            return boatCounter;
        }

O(N) solution: Get min weight minw. get max weight maxw in the list that is <= 150-m. Count the number of weights between minw and maxw - say this is count1.
Count the number of weights between maxw and 150. say this is count 2.
Answer is (count1 / 2)+count2.
No sorting is needed.This will take 4 passes on the list/array. O(N)

Operates in O(n log n) average time with O(n) memory

Assumptions: All individual weights are <= the max weight specified (what do you do with kids larger than the max weight? Leave them at the shore all sad?)

public static int countCanoes(int maxWeight, int[] weights){
    //sort the weights
    Arrays.sort(weights);
    //now pair off the weights that are collectively under maxWeight
    int loIndex = 0, hiIndex = weights.length - 1;
    int canoes = 0;
    while(loIndex <= hiIndex){
        int loWeight = weights[loIndex];
        int hiWeight = weights[hiIndex];
        if(loWeight + hiWeight <= maxWeight){
            loIndex++;
        }
        hiIndex--;
        canoes++;
    }
    return canoes;
}

Operating speed of O(nk) by bucket sorting the kids into their weight and then doing the same traversal. The amount of memory for this approach would be O(k). Could be faster when log n > kids weight.

JavaScript

var children = [ 100, 145, 33, 80, 9, 60, 30, 20 ];
children.sort(function(a,b){return a-b;});
i=0;
j=children.length-1;
num=0;
while  (i <= j){
	big = children[j];
	if (j==i)
		small = 0;
	else
		small = children[i];
	
	if ( small + big < 150 )
		i++;
	num++;
	j--;
}
alert (num);

output: 5

public static int count(int[] weights){
	  int[] arr = new int[151];
	  for(int w : weights){
	    ++arr[w];
	  }
	  int i = 0;
	  int j = arr.length-1;
	  int ret = 0;
	  for(;;){
	    for(; i < j && arr[i] == 0; ++i);
	    for(; j > i && arr[j] == 0; --j);
	    if (i >= j) break;
	    if (i+j <= 150){
	      --arr[i];
	      --arr[j];
	    } else {
	      --arr[j];
	    }
	    ++ret;
	  }
	
        if (i == j) {
            if (i*2 <= 150){
                ret += arr[i]/2;
                ret += arr[i]%2;
            } else {
                ret += arr[i];
            }
        }
	
	  return ret;
	}

It is a greedy problem

const int MAXW = 150;

int minCanoes(int A[], int n)
{
	sort(A, A + n);

	int ans = 0, lo = 0, hi = n - 1;

	while (lo < hi)
	{
		if (A[lo] + A[hi] <= MAXW) { ++lo; --hi; }

		else --hi;

		++ans;
	}

	if (lo == hi) ++ans;

	return ans;
}

#!/usr/bin/python
kids_by_weight = [40, 120, 122, 124, 156, 100, 140, 20, 50, 80, 30, 60, 80, 100, 40, 70, 30, 20]

kids_by_weight = sorted(kids_by_weight)
i =0
j =kids_by_weight.__len__() - 1
conoi = 0
while i < j:
        if(kids_by_weight[i] + kids_by_weight[j] <= 150):
                conoi += 1
                print "\nConoi[", conoi, "]: ", kids_by_weight[i], " and ", kids_by_weight[j]
                i += 1
                j -= 1
        elif(kids_by_weight[j] < 150):
                j -= 1
                conoi += 1
                print "\nConoi[", conoi, "]: ", kids_by_weight[j]
        elif(kids_by_weight[i] > 150):
                i += 1
                print "\nKid at Index:", i, " cannot be taken on conoi"
        elif(kids_by_weight[j] > 150):
                j -= 1
                print "\nKid at Index:", j, " cannot be taken on conoi"

print "\n Number of Conoi(s):",  conoi

Simple, sort the array of weights then use low index and high index pointers in order to pick every pair of kids with weights <= 150 then decrement both li and hi by 1, if you could not found this case, then pick up the kid with the larger weight and then decrement high index by 1.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CanoeCalculator {
	public static int calcMinimumCanoe(List<Integer> weights) {
		Collections.sort(weights);
		
		int li = 0, hi = weights.size() - 1, number = 0;
		
		
		while (li < hi) {
			if (weights.get(li) + weights.get(hi) <= 150) {
				++number;
				++li;
				--hi;
			} else if (weights.get(hi) <= 150) {
				++number;
				--hi;			
			} else {
				throw new RuntimeException("A kid weight cannot exceed 150!!!");
			}
		}
		
		if (li == hi) {
			++number;
		}
		
		
		return number;
	}

	public static void main(String[] args) {
		List<Integer> w1 = new ArrayList<Integer>();
		
		w1.add(30);
		w1.add(10);
		w1.add(15);
		w1.add(150);
		w1.add(50);
		
		System.out.println(CanoeCalculator.calcMinimumCanoe(w1));	
		
		List<Integer> w2 = new ArrayList<Integer>();
		
		w2.add(20);
		w2.add(10);
		w2.add(50);
		w2.add(60);
		
		System.out.println(CanoeCalculator.calcMinimumCanoe(w2));								
	}

}

Here is an O(nlogn) solution written in Python 3.4

def get_min_canoes(a):
    a.sort()
    if a[-1] > 150:
        raise Exception("weight exceeds max")
    left_walk = 0
    right_walk = len(a) - 1
    canoes = 0
    while left_walk < right_walk:
        if a[right_walk] + a[left_walk] <= 150:
            # can get two together
            left_walk += 1
        right_walk -= 1
        canoes += 1
    # if only 1 item left
    if right_walk == left_walk:
        canoes += 1
        return canoes
    return canoes


a = [1,149]

print(get_min_canoes(a))

def get_min_canoes(a):
    a.sort()
    if a[-1] > 150:
        raise Exception("weight exceeds max")
    left_walk = 0
    right_walk = len(a) - 1
    canoes = 0
    while left_walk < right_walk:
        if a[right_walk] + a[left_walk] <= 150:
            # can get two together
            left_walk += 1
        right_walk -= 1
        canoes += 1
    # if only 1 item left
    if right_walk == left_walk:
        canoes += 1
        return canoes
    return canoes


a = [1,149]

print(get_min_canoes(a))

Tom's solutions is the best so far. My solution does not beat it. It's just a different angle to think about this problem by dynamic programming.

If interested, follow this: cpluspluslearning-petert.blogspot.co.uk/2015/05/dynamic-programming-minimize-number-of.html

public void fitKidsInCanoe(int maxWeightPerCanoe, ArrayList<Integer> weights) {
        Collections.sort(weights);

        int canoes = 0;
        while (!weights.isEmpty()) {

            int left = weights.size() == 1 ? maxWeightPerCanoe : weights.get(0);
            int right = weights.get(weights.size() - 1);

            if (left + right <= maxWeightPerCanoe) {
                System.out.println("Coupled " + left + " : " + right);
                weights.remove(0);
                weights.remove(weights.size() - 1);
                canoes++;
            } else if (right <= maxWeightPerCanoe) {
                System.out.println("Alone " + right);
                weights.remove(weights.size() - 1);
                canoes++;
            } else {
                System.out.println("Left behind " + weights.remove(weights.size() - 1));
            }
            System.out.println("Total canoes: " + canoes);
        }
    }

The answer provided by Tom will work here.
As an extension to the problem assume If I also want to optimize the algorithm to transfer max weight as early as possible or say there are chipper options available if the Weight being transferred is lesser then max capacity of 150

I will take this approach in that case:
1. Sort the Boys by Weight in O(nLogn)
2. Iterate over array for each W from highest weight
3. Search for ( W-150) or just smaller to it
4. Transfer the couple of Boy and mark boys transferred. Hire the boat based on sum of weight of both boys
Repeat steps 3-4 till all boys are moved.

This have additional complexity but it is still O(nLog(n))

public int canons(int[] weights){
int number_of_canons = 0;
int pointer1 = 0;
int pointer2 = weights.length - 1;

//when there is just one kid
if(weights.length ==1)
return 1;

//sorting the weights
Arrays.sort(weights);

while(pointer1 <= pointer2){

//if any single kid weighs more than 150 it is not possible to accommodate him in any boat
//hence no number of boats can accommodate ALL kids. In that case, the function returns -1
if(weights[pointer2] > 150){
return -1;
}
int total_weight = weights[pointer1] + weights[pointer2];
if(total_weight <= 150)
pointer1++;

number_of_canons++;
pointer2--;
}

return number_of_canons;
}

public int canons(int[] weights){
           int number_of_canons = 0;
           int pointer1 = 0;
           int pointer2 = weights.length - 1;
           
           //when there is just one kid
           if(weights.length ==1)
               return 1;
           
           //sorting the weights
           Arrays.sort(weights);
           
           while(pointer1 <= pointer2){
             
               //if any single kid weighs more than 150 it is not possible to accommodate him in any boat
               //hence no number of boats can accommodate ALL kids. In that case, the function returns -1
               if(weights[pointer2] > 150){
                   return -1;
               }
               int total_weight = weights[pointer1] + weights[pointer2];
               if(total_weight <= 150)
                pointer1++;
               
               number_of_canons++;
               pointer2--;
           }
       
       return number_of_canons;     
    }

public class CanoesNeeded {

	static final int canoeMAX = 150;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] kids = {35,110, 111, 111, 114, 115, 149, 150};
		System.out.println("Canoes Needed: "+getMinCanoes(kids));
	}
	
	public static int getMinCanoes(int [] kids){
		int canoes = 0;
		Arrays.sort(kids);
		for(int i=0,j=kids.length-1;i<=j;canoes++){
			if(i==j){
				System.out.println("Kid "+kids[i]+" gets his own canoe");
				canoes+=1;
				break ;
			}
			if(kids[i]+kids[j]>canoeMAX){
				System.out.println("Kid "+kids[j]+" gets a canoe");
				j--;
			}
			else{
				System.out.println("Kids "+kids[i]+" & "+kids[j]+" share a canoe");
				j--;
				i++;
			}
		}
		return canoes;
	}
}

This is a O(n log n) solution because of the array sorting. Otherwise one pass over the weights is enough to solve the problem.

Sort the kids based upon their weights
Start with two pointers, one at the highest weight kid and another is at lowest weight kid
Check if both can be in a single canoe or not, if not, reserve one for higher weight kid, decrement its counter,
if yes, then reserve one for both of them, and increase and decrease the counters of respective kids.

Complexity : O(nlog(n))
Space : O(1)

There is a case where all the kids have a weight bigger that 150

public int GetNumCanoes(int[] weights, int maxWeight)
{
	Array.Sort(weights);

	int start = 0;
	int end = weights.Length - 1;
	int numCanoes = 0;

	while (start <= end)
	{
		if (weights[start] > maxWeight)
			start++;
		else if (weights[end] > maxWeight)
			end--;
		else if (start <= end)
		{
			numCanoes++;
			// If the sum is bigger that maxWeight they can't go an the same canoe, lets try in the next iteration
			if (weights[start] + weights[end] <= maxWeight)
				start++;
			end--;
		}
	}

	return numCanoes;
}

1. sort the kids by weight
2. take 2 pointers high and low pointing to first and last kid in the sorted array
3. while ( low < high) {

if(A[high] > 150 || A[low]+ a[high] > 150)
high --; count++;
else if (A[low] + A[high] < = 150)
high--; low++; count++;
}
return count;

complexity = O(nlogn)