title: Codility NailingPlanks
body: <p>Tried to understand the solution for Codility NailingPlanks. </p>
  
  <p>Link for the Problem: 
  <a href="https://app.codility.com/programmers/lessons/14-binary_search_algorithm/nailing_planks/" rel="noreferrer">https://app.codility.com/programmers/lessons/14-binary_search_algorithm/nailing_planks/</a></p>
  
  <blockquote>
    <p>You are given two non-empty arrays A and B consisting of N integers.
    These arrays represent N planks. More precisely, A[K] is the start and
    B[K] the end of the K−th plank.</p>
    
    <p>Next, you are given a non-empty array C consisting of M integers. This
    array represents M nails. More precisely, C[I] is the position where
    you can hammer in the I−th nail.</p>
    
    <p>We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I]
    such that A[K] ≤ C[I] ≤ B[K].</p>
    
    <p>The goal is to find the minimum number of nails that must be used
    until all the planks are nailed. In other words, you should find a
    value J such that all planks will be nailed after using only the first
    J nails. More precisely, for every plank (A[K], B[K]) such that 0 ≤ K
    &lt; N, there should exist a nail C[I] such that I &lt; J and A[K] ≤ C[I] ≤
    B[K].</p>
  </blockquote>
  
  <p>Link for the solution: 
  <a href="https://github.com/ZRonchy/Codility/blob/master/Lesson12/NailingPlanks.java" rel="noreferrer">https://github.com/ZRonchy/Codility/blob/master/Lesson12/NailingPlanks.java</a></p>
  
  <pre><code>import java.util.Arrays;
  
  class Solution {
      public int solution(int[] A, int[] B, int[] C) {
          // the main algorithm is that getting the minimal index of nails which
          // is needed to nail every plank by using the binary search
          int N = A.length;
          int M = C.length;
          // two dimension array to save the original index of array C
          int[][] sortedNail = new int[M][2];
          for (int i = 0; i &lt; M; i++) {
              sortedNail[i][0] = C[i];
              sortedNail[i][1] = i;
          }
          // use the lambda expression to sort two dimension array
          Arrays.sort(sortedNail, (int x[], int y[]) -&gt; x[0] - y[0]);
          int result = 0;
          for (int i = 0; i &lt; N; i++) {//find the earlist position that can nail each plank, and the max value for all planks is the result
              result = getMinIndex(A[i], B[i], sortedNail, result);
              if (result == -1)
                  return -1;
          }
          return result + 1;
      }
      // for each plank , we can use binary search to get the minimal index of the
      // sorted array of nails, and we should check the candidate nails to get the
      // minimal index of the original array of nails.
      public int getMinIndex(int startPlank, int endPlank, int[][] nail, int preIndex) {
          int min = 0;
          int max = nail.length - 1;
          int minIndex = -1;
          while (min &lt;= max) {
              int mid = (min + max) / 2;
              if (nail[mid][0] &lt; startPlank)
                  min = mid + 1;
              else if (nail[mid][0] &gt; endPlank)
                  max = mid - 1;
              else {
                  max = mid - 1;
                  minIndex = mid;
              }
          }
          if (minIndex == -1)
              return -1;
          int minIndexOrigin = nail[minIndex][1];
          //find the smallest original position of nail that can nail the plank
          for (int i = minIndex; i &lt; nail.length; i++) {
              if (nail[i][0] &gt; endPlank)
                  break;
              minIndexOrigin = Math.min(minIndexOrigin, nail[i][1]);
              // we need the maximal index of nails to nail every plank, so the
              // smaller index can be omitted    ****
              if (minIndexOrigin &lt;= preIndex) // ****
                  return preIndex;            // ****
          } 
          return minIndexOrigin;
      }
  }
  </code></pre>
  
  <p>I don't understand Line 99-102, marked with <code>****</code>, of the solution.</p>
  
  <p>My question is: </p>
  
  <p>If <code>minIndexOrigin &lt;= preIndex</code> , then it will use <code>preIndex</code>, 
  but how if the <code>preIndex</code> doesn't nail the current plank ? </p>
  
  <p>Is there a bit mistake with the solution ? </p>