How to improve the efficiency of the algorithm whi

Question

This is the question: There are N boys and N girls. Only a boy and a girl can form a dancing pair (i.e. no same sex dancing pairs are allowed). The only other condition in making pairs is that their absolute difference in height should be less than or equal to K.

Find the maximum number of pairs that can be formed so that everyone has a unique partner.

I want to improve my algorithm to take less time.. first see the code:

    //k is the maximum difference between pairs 
    int k = 5;
    ArrayList<Integer> ArrBoys = new ArrayList<>(Arrays.asList(new Integer[]{28, 16, 22}));
    ArrayList<Integer> ArrGirls = new ArrayList<>(Arrays.asList(new Integer[]{13, 10, 14}));

    //sorting all arrays
    Collections.sort(ArrBoys);
    Collections.sort(ArrGirls);

    System.out.println("After Sorting");

    //printing arrays after sorting
    for (Integer ArrBoy : ArrBoys) {
        System.out.print(ArrBoy + " ");
    }
    System.out.println("");
    for (Integer ArrGirl : ArrGirls) {
        System.out.print(ArrGirl + " ");
    }
    System.out.println("");

    //algorithm used to find the number of pairs
    int count = 0;
    for (Iterator<Integer> iteB = ArrBoys.iterator(); iteB.hasNext();) {
        Integer ArrBoy = iteB.next();
        for (Iterator<Integer> iteG = ArrGirls.iterator(); iteG.hasNext();) {
            {
                Integer ArrGirl = iteG.next();
                int dif = (int) Math.abs(ArrBoy - ArrGirl);
                if (dif <= k) {
                    System.out.println("we took " + ArrBoy + " from boys with "
                            + ArrGirl + " from girls, thier dif < " + k);
                    ArrBoys.remove(ArrBoy);
                    ArrGirls.remove(ArrGirl);
                    iteB = ArrBoys.iterator();
                    count++;
                    break;
                } else {
                    System.out.println("we try " + ArrBoy + " from boys with " + ArrGirl + " from grils but thier dif > " + (int) k);
                    //ArrGirls.remove(ArrGirl);                   
                }
            }

        }
    }
    System.out.println("the number of pairs we can take is "+count);

the output of this code is:

As you see this algorithm inefficient since we don't need to start comparing the height from the first girl for the second boy, we should go to the girl which come after the previous girl we took as pair.

For example: in the boy with 22 height, the algorithm must start comparing the boys'height with the girl with 14 height, because we already sort them, if the first boy (shorter) cant make a pair with the first girl so definitely the second boy (longer) cant also, we waste the time if we compare from the first girl.

We can solve this problem by two choices, either by making the iterator start with the girl after the previous boy has been stopped (i don't know how to do it with iterator), or by removing the girl from the arraylist once if it's not satisfy the condition and let the loop start with first girl (i tried this but it gives me an exception)

Solve it by these two ways if you can...

Answer 1

You have to add more conditions. Here it is, there are three options :

• abs(dif) <= k : they can dance together
• dif > k : even the current boy (the smallest) is too tall for her, no one can dance with her, exclude her
• dif < -k : the first girl is far too tall for him, exclude him

Here is the code:

int count = 0;
int gLimit = 0;
for (int b = 0; b<ArrBoys.size();b++) {
    if(gLimit == ArrGirls.size()) {
        System.out.println("no more girl for boy " + ArrBoys.get(b));
    }
    for (int g = gLimit; g<ArrGirls.size();g++) {
        {

            int dif = ArrBoys.get(b) - ArrGirls.get(g);
            if (Math.abs(dif) <= k) {
                System.out.println("we took " + ArrBoys.get(b) + " from boys with "
                        + ArrGirls.get(g) + " from girls, thier dif < " + k);
                gLimit++;
                count++;
                break;
            } else if (dif > k) {
                System.out.println("we try " + ArrBoys.get(b) + " from boys with " + ArrGirls.get(g) + " from grils but thier dif > " + (int) k + ", girl too small, excluded");
                gLimit++;
            } else if (dif < -k) {
                System.out.println("we try " + ArrBoys.get(b) + " from boys with " + ArrGirls.get(g) + " from grils but thier dif > " + (int) k + ", boy too small, excluded");
                break;
            }
        }
    }
}

I used get index for more maniability on lists content

Here is the ouput

After Sorting
16 22 28 
10 13 14 
we try 16 from boys with 10 from grils but thier dif > 5, girl too small, excluded
we took 16 from boys with 13 from girls, thier dif < 5
we try 22 from boys with 14 from grils but thier dif > 5, girl too small, excluded
no more girl for boy 28
the number of pairs we can take is 1