Tried to understand the solution for Codility NailingPlanks.
Link for the Problem: https://app.codility.com/programmers/lessons/14-binary_search_algorithm/nailing_planks/
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.
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.
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].
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 < N, there should exist a nail C[I] such that I < J and A[K] ≤ C[I] ≤ B[K].
Link for the solution: https://github.com/ZRonchy/Codility/blob/master/Lesson12/NailingPlanks.java
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 < 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[]) -> x[0] - y[0]);
int result = 0;
for (int i = 0; i < 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 <= max) {
int mid = (min + max) / 2;
if (nail[mid][0] < startPlank)
min = mid + 1;
else if (nail[mid][0] > 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 < nail.length; i++) {
if (nail[i][0] > 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 <= preIndex) // ****
return preIndex; // ****
}
return minIndexOrigin;
}
}
I don't understand Line 99-102, marked with ****, of the solution.
My question is:
If minIndexOrigin <= preIndex , then it will use preIndex,
but how if the preIndex doesn't nail the current plank ?
Is there a bit mistake with the solution ?
The case that is handled in those lines is when you find that there is an index that nails the current plank, which index is less (or equal) to the lowest index we need to be able to nail another (previously analysed) plank. In that case, we don't need to look further for the current plank, since we know that:
Since we are only interested in the greatest index among the least indexes we need for the different planks (i.e. the index for the "worst" plank), we know that the index we just found now is not important any more: if we already know that we will be using all the nails up to at least preIndex, we know that one nail among that set will nail the current plank. We can just exit the loop and return a "dummy" index that will not influence the result.
Note what the effect is in the calling loop:
result = getMinIndex(A[i], B[i], sortedNail, result);
After this assignment, result will be equal to what result was before the call: this plank (A[i], B[i]) can be nailed with an earlier nail, but we don't really care which nail that is, as we need to know the worst case, which is up to now reflected by result, and all nails up to that index are already in the set of nails that will be hammered.
You can compare it with alpha-beta pruning.