title: How to improve the efficiency of the algorithm while using Iterator in java?
body: <p>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.</p>
  
  <p>Find the maximum number of pairs that can be formed so that everyone has a unique partner.</p>
  
  <p>I want to improve my algorithm to take less time..
  first see the code:</p>
  
  <pre><code>    //k is the maximum difference between pairs 
      int k = 5;
      ArrayList&lt;Integer&gt; ArrBoys = new ArrayList&lt;&gt;(Arrays.asList(new Integer[]{28, 16, 22}));
      ArrayList&lt;Integer&gt; ArrGirls = new ArrayList&lt;&gt;(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&lt;Integer&gt; iteB = ArrBoys.iterator(); iteB.hasNext();) {
          Integer ArrBoy = iteB.next();
          for (Iterator&lt;Integer&gt; iteG = ArrGirls.iterator(); iteG.hasNext();) {
              {
                  Integer ArrGirl = iteG.next();
                  int dif = (int) Math.abs(ArrBoy - ArrGirl);
                  if (dif &lt;= k) {
                      System.out.println("we took " + ArrBoy + " from boys with "
                              + ArrGirl + " from girls, thier dif &lt; " + 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 &gt; " + (int) k);
                      //ArrGirls.remove(ArrGirl);                   
                  }
              }
  
          }
      }
      System.out.println("the number of pairs we can take is "+count);
  </code></pre>
  
  <p>the output of this code is:</p>
  
  <p><img src="https://i.stack.imgur.com/DG31p.png" alt="enter image description here"></p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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)</p>
  
  <p>Solve it by these two ways if you can...</p>