Problem

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].

For example, given arrays A, B such that: 

    A[0] = 1    B[0] = 4

    A[1] = 4    B[1] = 5

    A[2] = 5    B[2] = 9

    A[3] = 8    B[3] = 10

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10]. 

Given array C such that:

    C[0] = 4

    C[1] = 6

    C[2] = 7

    C[3] = 10

    C[4] = 2 

if we use the following nails:

·         0, then planks [1, 4] and [4, 5] will both be nailed.

·         0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.

·         0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.

·         0, 1, 2, 3, then all the planks will be nailed.

Thus, four is the minimum number of nails that, used sequentially, allow all the planks to be nailed. 

Write a function:

    function solution(A, B, C);

that, given two non-empty arrays A and B consisting of N integers and a non-empty array C consisting of M integers, returns the minimum number of nails that, used sequentially, allow all the planks to be nailed.

If it is not possible to nail all the planks, the function should return -1. 

For example, given arrays A, B, C such that:

    A[0] = 1    B[0] = 4

    A[1] = 4    B[1] = 5

    A[2] = 5    B[2] = 9

    A[3] = 8    B[3] = 10

    C[0] = 4

    C[1] = 6

    C[2] = 7

    C[3] = 10

    C[4] = 2 

the function should return 4, as explained above.

Write an efficient algorithm for the following assumptions:

·         N and M are integers within the range [1..30,000];

·         each element of arrays A, B and C is an integer within the range [1..2*M];

·         A[K] ≤ B[K]. 

Note:

Assume that the planks are on one straight line and all have the same small thickness.

Assume that the planks are on a flat floor. 

The intention of nailing a plank, is to nail it to the floor. In the course of nailing, a nail may pass through an additional one or more planks before reaching the floor.

In the example of the problem, the minimum number of nails are obtained with nails from the C array, at indexes 0, 1, 2 and 3. From the array, C, the nails are at positions 4, 6, 7 and 10, on the floor. At these 4 positions, all the planks are nailed. 

If the nail at index 4 of the C array for position 2 is nailed, that would take the number of nails unnecessarily to 5, since plank [1,4] has already been nailed at position 4.

Clarification

Imagine that 2*M integers are written on the floor for 2*M points, from 1 to 2*M on a straight line. For the given example, M is 5 and so 2*M is 10. The maximum number of nails is 2xM, which is one of the assumptions given. The following table shows the position numbers (integer) and the planks on the floor:

The planks are in light gray. Array C is: C[0] = 4, C[1] = 6, C[2] = 7, C[3] = 10, C[4] = 2. The smallest position for a nail is 2 of C[4]. If a nail is hammered at position 2, plank [1,4] will be nailed. However, there is a nail for position 4 of C[0]. If a nail is hammered at position 4, plank [1,4] and plank [4,5] will be nailed. That is, two planks nailed with one nail. So, one nail should be nailed at position 4, and the nail for position 2 omitted, in order to reduce the number of nails. The question wants the smallest number of nails to have all planks nailed. 

C[1] = 6 and C[2] = 7, and both would nail just 1 plank. So only one of these nails should be used, making the minimum number of nails employed so far, as 2. C[3] = 10 and if this nail is used, plank [8,10] would be nailed, and thus, all 4 planks nailed. So, the minimum number of nails needed to nail all the four planks is 3.

However, the task says that the minimum number of nails is 4; which are C[0] = 4, C[1] = 6, C[2] = 7, C[3] = 10. Note that either C[1] = 6 or C[2] = 7 should have been used. The solution for Task score : 100% -  Correctness : 100% ; Performance : 100% at app.codility.com/programmers, also gives 4 as the answer (minimum number of nails). The fast solution, presented in this document, also gives 4 as the minimum number of nails. A fast solution that would give 3 as the minimum number of nails, is not addressed in this document. 

Why is 4 the correct answer for this problem? A quotation from the problem description is:

"In other words, you should find a value J such that all planks will be nailed after using only the first J nails." The nails are from the C array. The first 4 nails are: 4, 6, 7, 10. Though either nail 6 or nail 7 is redundant, the problem wants the required nails to be in sequence, beginning from the first nail. With that, 4 is the correct answer, and not 3.

Strategy

Start with a maximum of 2*M (10) nails. Use binary search algorithm and be coming down, by dividing interval limits by 2. A target or a tentative target is the tentative minimum number of nails. For each tentative target, another function verifies if those number of nails will nail all the planks. If Yes (true), it does not necessarily mean that, that target is the minimum number of nails. Division of the interval limits still has to take place to be sure that the next tentative target down, is the minimum number of nails. This division continues until the binary search algorithm finishes in O(log₂n) time. This is a special kind of binary search algorithm. The verification of the tentative target number of nails to nail all the planks, adds extra time.

If the verification returns No (false), then binary search will go to the upper (right) half of the interval. 

There are two functions, called solution() and CheckAllPlanksNailed(). solution() has the binary search code, and CheckAllPlanksNailed() does the checking to return true or false.

Fast Program

The fast program is (read the code and comments): 

<script type='text/javascript'>
    "use strict";  

    function CheckAllPlanksNailed(A, B, C, nail_count) {
        let M = C.length;
        let N = A.length;
        const countPresence = new Array(2*M+1).fill(0);
 
        for (let i = 0; i < nail_count; i++) {
            countPresence[C[i]] = 1;
        }

        for (let i = 1; i < countPresence.length; i++) {
            countPresence[i] = countPresence[i] + countPresence[i - 1];
        }

        let all_nailed = true;
        for (let i = 0; i < N && all_nailed; i++) {
            all_nailed = countPresence[B[i]] - countPresence[A[i]-1] > 0;
        }
    
        return all_nailed;
    }

    function solution(A, B, C) {
        let M = C.length;
        let result = -1;

        let minNails = 1;    //from an assumption
        let maxNails = 2*M;    //from an assumption

        while (minNails <= maxNails) {
            let mid = parseInt((maxNails + minNails) / 2);    //assumed minimum
            if (CheckAllPlanksNailed(A, B, C, mid)) {
                maxNails = mid - 1;
                result = mid;
            }
            else {
                minNails = mid + 1;
            }
        }

        return result;
    }


    let A = [1, 4, 5, 8];
    let B = [4, 5, 9, 10];

    let C = [4, 6, 7, 10, 2];

    let ret = solution(A, B, C);

    document.write(ret + '<br>'); 

</script>

The output is 4. 

At app.codility.com/programmers the scoring and detected time complexity for this solution() is:

    Task score : 100% -  Correctness : 100% ; Performance : 100%

    Detected time complexity : O((N + M) * log(M))

The checking function is: 

    function CheckAllPlanksNailed(A, B, C, nail_count) {
        let M = C.length;
        let N = A.length;
        const countPresence = new Array(2*M+1).fill(0);
 
        for (let i = 0; i < nail_count; i++) {
            countPresence[C[i]] = 1;
        }

        for (let i = 1; i < countPresence.length; i++) {
            countPresence[i] = countPresence[i] + countPresence[i - 1];
        }

        let all_nailed = true;
        for (let i = 0; i < N && all_nailed; i++) {
            all_nailed = countPresence[B[i]] - countPresence[A[i]-1] > 0;
        }
    
        return all_nailed;
    }

The countPresence array has length 2*M+1. The +1 is there just in case a position is 0. All the cells in this array are initialized to 0. The indexes of this count array represent all the possible values that the C array can have. These are all the possible positions; 10 in the above example. 

The next code segment puts 1, for one nail, as value for an index in the count array (countPresence), where an index is value in the C array. This means that, for any value that is not in the C array, its index in the countPresence array has 0 as value. For the problem example above, the count array (countPresence) is:

The next code segment determines the running sums in the count array. For the problem example above, it is:

This is prefix summing shifted one place to the right. 

The next code segment determines if each of the planks has at least one nail. If one value in the running (prefix) sums table is subtracted from another value in the same table, on the right, to give a value greater than 0, it means that there is at least one nail between those two positions along the length of all the planks. If the difference is 0, it means that there is no nail between the positions.  The main statement for this last code segment is:

        all_nailed = countPresence[B[i]] - countPresence[A[i]-1] > 0; 

This is a Boolean expression, which will make the all_nailed variable, hold true or false. When all_nailed becomes false, the next iteration of the loop is not executed.

Thanks for reading.