Celebration Party Problem - Algorithm

Question

I solved the following problem:

Let's consider the following situation. You've invited a lot of children to a celebration party, and you want to entertain them and also teach them something in the process. You are going to hire a few teachers and divide the children into groups and assign a teacher to each of the groups. This teacher will work with this group through the whole party.

But you know that for a teacher to work with a group of children efficiently children of that group should be of relatively the same age. More specifically age of any two children in the same group should differ by at most, one year.

Also, you want to minimize the number of groups. Because you want to hire fewer teachers, and spend the money on presents and other kinds of entertainment for the children. So, you need to divide children into the minimum possible number of groups. Such that the age of any two children in any group differs by at most one year.

import java.io.*;
import java.util.*;

public class ChildrenGroup{

  static int getGroups(float[] children) {

    int lastChild = children.length;
    int currentChild=1;
    int startingPoint=0;
    int groups=0;

    while(currentChild<lastChild){

        if(children[currentChild]-children[startingPoint]>1){
            startingPoint=currentChild ;
            groups++;
        }


        if(currentChild==lastChild-1){
            groups++;
        }
        currentChild++;
    }


    return groups;
  }

  public static void main(String[] args) {

    Scanner in = new Scanner(System.in);

    int n = in.nextInt();
    float[] children = new float[n];

    for (int i = 0; i < n; i++) {
        children[i] = in.nextFloat();
    }

    System.out.println(getGroups(children));

  }
}

Sample input 1:

7
2.5 3.2 3.5 4.0 4.8 5.2 6.0

Output 1:

3

Sample input 2:

3
2.1 4.5 6.7

Output 2:

3

What's your thoughts on the solution?

Answer 1

Your algorithm is correct and will be very efficient. Note that it assumes that the array of float values is sorted ascendingly. To make sure of that, you could explicitely sort the array before entering the while loop, or document that the method must take a pre-sorted array.

The comments I have are concerning the presentation of the code itself:

• Consider adding white-spaces before and after each parentheses and curly braces. For example

  while(currentChild<lastChild){
  

  could be read easier with

  while (currentChild < lastChild) {
  

  where extra spaces have been added.

• You have added a lot of vertical spaces. Adding a line break with an empty line can indeed help readability but having 2 empty lines is too much: this is what you have after your while loop and between the two if statements. Consider having only a single empty line where you think it adds to clarity.

• Be consistent with your usage of white-spaces. Statements like

  startingPoint=currentChild ;
  

  are a bit weird. There is a space before the semi-colon and no spaces around the = operator.

An IDE can usually reformat your code automatically. For example, taking directly your code into Eclipse and reformatting it by selecting it and hitting Ctrl+Shift+F let me to

static int getGroups(float[] children) {

    int lastChild = children.length;
    int currentChild = 1;
    int startingPoint = 0;
    int groups = 0;

    while (currentChild < lastChild) {

        if (children[currentChild] - children[startingPoint] > 1) {
            startingPoint = currentChild;
            groups++;
        }

        if (currentChild == lastChild - 1) {
            groups++;
        }
        currentChild++;
    }

    return groups;
}

---

Also, I noticed that you used wildcard import statement:

import java.io.*;
import java.util.*;

This is generally not a good practice. You want to import the specific classes with which you are interacting. In this case, it is actually not a lot, you just one import statement:

import java.util.Scanner;

There is no need for any class under java.io.