Massive Algorithms: Codility Lesson 12

Codility Lesson 12 - Nailing Planks

https://codility.com/programmers/lessons/12

You are given two non-empty zero-indexed 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 zero-indexed 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:

int solution(int A[], int B[], int N, int C[], int M);

that, given two non-empty zero-indexed arrays A and B consisting of N integers and a non-empty zero-indexed 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.

https://codesolutiony.wordpress.com/2015/01/14/codility-12-2-nailingplanks/

    public int solution(int[] A, int[] B, int[] C) {

        int[][] posMap = new int[C.length][2];

        for (int i = 0; i < C.length; i++) {

            posMap[i][0] = C[i];

            posMap[i][1] = i;

}

        Arrays.sort(posMap, new Comparator<int[]>(){

            public int compare(int[] a, int[] b) {

                return Integer.compare(a[0], b[0]);

}

});

        int result = 0;

        for (int i = 0; i < A.length; i++) {//find the earlist position that can nail each plank, and the max value for all planks is the result

            int tmp = findNail(A[i], B[i], posMap, result);

            if (tmp == -1 || tmp == A.length - 1) {

                return tmp == -1 ? tmp : tmp + 1;

}

            result = Math.max(result, tmp);

}

        return result + 1;

}

    private int findNail(int plankStart, int plankEnd, int[][] posMap, int prePos) {

        int start = 0;

        int end = posMap.length - 1;

        int pos = -1;

        while (start <= end) {

            int mid = (start + end) / 2;

            if (posMap[mid][0] > plankEnd) {

                end = mid - 1;

            } else if (posMap[mid][0] < plankStart) {

                start = mid + 1;

            } else {

                pos = mid; //get the original position of the nail

                end = mid - 1;

}

}

        if (pos == -1) {

            return pos;

}

        int result = posMap[pos][1];

        //find the smallest original position of nail that can nail the plank

        for (int i = pos + 1; i < posMap.length; i++) {

            if (posMap[i][0] > plankEnd) {

                break;

}

            result = Math.min(result, posMap[i][1]);

            if (result <= prePos) {//very important, otherwise TLE

                return prePos;

}

}

        return result;

}

https://github.com/jlhuang/codility-lessons/blob/master/lesson%2012%20:%20Binary%20search%20algorithm/NailingPlanks/Solution.java
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++) {
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];
// this check is to get the minimal index of the original array of nails
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;
}

https://github.com/acprimer/Codility/blob/master/src/Lesson12/NailingPlanks.java
// https://codility.com/demo/results/demoNQZADS-QJU/
// TLE
public int solution(int[] A, int[] B, int[] C) {
boolean[] vis = new boolean[A.length];
int count = 0;
for (int i = 0; i < C.length; i++) {
for (int j = 0; j < A.length; j++) {
if (!vis[j] && A[j] <= C[i] && C[i] <= B[j]) {
vis[j] = true;
count++;
}
}
if (count >= A.length) return i + 1;
}
return -1;
}
http://www.martinkysel.com/codility-nailingplanks-solution/
to-do: http://codesays.com/2014/solution-to-nailing-planks-by-codility/
http://blog.csdn.net/caopengcs/article/details/41834173

更快的算法，如果我们建立一个长度为2 * M的数组，每个位置表示该位置上钉子的最小编号（可能同一个位置有多个钉子，取编号最小的），没有钉子的位置值为无穷大。那么固定第i块木板的最小编号钉子，相当于[A[i],B[i]]区间的最小值。但是我们这个题实际上是求这些最小值的max，首先如果一个木板A的覆盖区间完全包含另外一个木板B,则实际上我们只考虑木板B即可。因为固定木板B同时能固定木板A，并且我们一定要固定木板B，即使A覆盖区间有更小的值，也无法改变最终取最大值的结果。

于是，我们可以建立一个数组plank[x]表示右端点为x的木板的最大左边界，没有木板的话，认为边界是0。我们从左到右遍历木板右边界，假设这之前（更左）的木板已经被固定了，已经固定的区间范围是[left,right) (右开区间），然后对当前这个木板，如果显然它的右边界更大（我们遍历右边界是按当增的顺序），如果该木板start <= left,则它已经被前面固定住了，不影响结果。否则，要求[start,end]之间的最大值。这个问题有点像滑动窗口最大值的问题。本质在于：我们不断查询最大值，每次查询的时候窗口的左边界和右有边界是单调递增的，于是我们可以动态更新窗口维护最大值。这个经典问题可以用单调队列实现，这也是把单调队列发挥到了极致。

结论：查询窗口最大值的时候，如果窗口向右滑动的过程中，查询时左边界和右边界都是单增的，则可以使用单调队列解决。

时间复杂度 O(N + M)达到了线性。

const int inf = 2000000000;
int solution(vector<int> &A, vector<int> &B, vector<int> &C) {
    // write your code in C++98
    int m = C.size(), M = (m << 1) | 1;
    vector<int> nail(M, inf);
    for (int i = m - 1; i >= 0; --i) {
        nail[C[i]] = i;
    }
    vector<int> plank(M, 0);
    for (int i = 0; i < A.size(); ++i) {
        plank[B[i]] = max(plank[B[i]], A[i]);
    }
    int left = 0, right = 0, r = 0;
    deque<int> q;
    for (int i = 1; i < M; ++i) {
        if (plank[i] > left) {
            left = plank[i];
            while ((!q.empty()) && (q.front() < left)) {
                q.pop_front();
            }
            for (right = max(right, left); right <= i; ++right) {
                while ((!q.empty()) && (nail[q.back()] >= nail[right])) {
                    q.pop_back();
                }
                q.push_back(right);
            }
            r = max(r, nail[q.front()]);
            if (r >= inf) {
                return -1;
            }
        }
    }
    return r + 1;
}

http://codility-lessons.blogspot.com/2015/03/lesson-11-nailingplanks-nailing-planks.html

Codility Lesson 12 - Nailing Planks

Labels

Popular Posts