Codness钉板

尝试了解Codility NailingPlanks的解决方案。

问题链接： https://app.codility.com/programmers/lessons/14-binary_search_algorithm/nailing_planks/

您将看到由N个整数组成的两个非空数组A和B。 这些数组代表N个板。更准确地说，A[K]是起点， B[K]第K−板的末尾。

接下来，您将看到一个由M个整数组成的非空数组C。这 数组表示M个钉子。更准确地说，C[i]是 你可以把I−TH钉子钉进去。

如果存在一个钉子C[i]，我们称板子(A[K]，B[K])为钉子 使得A[K]≤C[I]≤B[K]。

目标是找到必须使用的最少数量的钉子 直到所有的木板都钉好。换句话说，您应该找到一个 值J，使得所有木板在仅使用第一个木板后都将被钉上钉子 J钉子。更准确地说，对于每个板(A[K]，B[K])，使得0≤K <；N，应该存在一个钉子C[I]，使得I<；J和A[K]≤C[I]≤ B[K].

解决方案的链接： 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;
    }
}

我看不懂解决方案中标有****的第99-102行。

我的问题是：

如果minIndexOrigin <= preIndex，则它将使用preIndex， 但如果preIndex没有钉住当前的木板怎么办？

解决方案是否有一点错误？

---

解决方案

在这些行中处理的情况是，当您发现存在一个钉住当前板的索引时，该索引小于(或等于)我们需要能够钉住另一个(先前分析过的)板所需的最低索引。在这种情况下，我们不需要进一步查找当前的板，因为我们知道：

• 我们可以钉木板
• 我们可以使用不大于其他板真正需要的索引的索引。

因为我们只对不同木板所需的最少索引中的最大索引感兴趣(即，"最差"木板的索引)，所以我们知道现在找到的索引不再重要：如果我们已经知道将使用至少到preIndex的所有钉子，我们知道该集合中的一个钉子将钉住当前的木板。我们只需退出循环并返回一个不会影响结果的"伪"索引。

注意调用循环中的效果：

result = getMinIndex(A[i], B[i], sortedNail, result); 

在此赋值后，result将等于调用之前的result：这块木板(A[i], B[i])可以用更早的钉子钉住，但我们并不真正关心是哪根钉子，因为我们需要知道最坏的情况，这是到目前为止由result反映的，并且所有达到该索引的钉子都已经在将被锤打的钉子集中。

您可以将其与阿尔法-贝塔修剪进行比较。