Count the minimum number of nails that allow a series of planks to be nailed.
- Difficulty Level: Medium
- Question URL: https://app.codility.com/programmers/lessons/14-binary_search_algorithm/nailing_planks/
- Time Complexity:
Solution:
Solution to Codility's Nailing Planks problem which is from the Codility Lesson 14: Binary search algorithm and, is solved in Java 8 with 100% performance and correctness scores. The goal here is to count the minimum number of nails that allow a series of planks to be nailed. You can find the question of this NailingPlanks problem in the Codility website.
package Codility.Lesson14;
import java.util.*;
public class NailingPlanks {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a1 = { 1, 4, 5, 8 };
int[] a2 = { 4, 5, 9, 10 };
int[] a3 = { 4, 6, 7, 10, 2 };
int result1 = solution(a1, a2, a3);
System.out.println(result1);
}
public static 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 static 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;
}
}