Codility 钉板

Question

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

\n\n

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

\n\n

\n

给定两个由 N 个整数组成的非空数组 A 和 B。\n 这些数组代表 N 个木板。更准确地说，A[K] 是第 K\xe2\x88\x92 个木板的起点，\n B[K] 是终点。

\n\n

接下来，给出一个由 M 个整数组成的非空数组 C。该数组代表 M 个钉子。更准确地说，C[I] 是您可以敲入第 I\xe2\x88\x92 个钉子的位置。

\n\n

如果存在钉子 C[I]\n 使得 A[K] \xe2\x89\xa4 C[I] \xe2\x89\ ，我们说木板 (A[K], B[K]) 被钉住xa4 B[K]。

\n\n

目标是找到必须使用的最少钉子数量，直到钉完所有木板。换句话说，您应该找到一个值 J，使得仅使用前 J 个钉子后即可钉好所有木板。更准确地说，对于每个木板 (A[K], B[K]) 使得 0 \xe2\x89\xa4 K\n < N，应该存在一个钉子 C[I] 使得 I < J 且 A[K ] \xe2\x89\xa4 C[I] \xe2\x89\xa4\n B[K]。

\n

\n\n

解决方案链接：\n https://github.com/ZRonchy/Codility/blob/master/Lesson12/NailingPlanks.java

\n\n

import java.util.Arrays;\n\nclass Solution {\n    public int solution(int[] A, int[] B, int[] C) {\n        // the main algorithm is that getting the minimal index of nails which\n        // is needed to nail every plank by using the binary search\n        int N = A.length;\n        int M = C.length;\n        // two dimension array to save the original index of array C\n        int[][] sortedNail = new int[M][2];\n        for (int i = 0; i < M; i++) {\n            sortedNail[i][0] = C[i];\n            sortedNail[i][1] = i;\n        }\n        // use the lambda expression to sort two dimension array\n        Arrays.sort(sortedNail, (int x[], int y[]) -> x[0] - y[0]);\n        int result = 0;\n        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\n            result = getMinIndex(A[i], B[i], sortedNail, result);\n            if (result == -1)\n                return -1;\n        }\n        return result + 1;\n    }\n    // for each plank , we can use binary search to get the minimal index of the\n    // sorted array of nails, and we should check the candidate nails to get the\n    // minimal index of the original array of nails.\n    public int getMinIndex(int startPlank, int endPlank, int[][] nail, int preIndex) {\n        int min = 0;\n        int max = nail.length - 1;\n        int minIndex = -1;\n        while (min <= max) {\n            int mid = (min + max) / 2;\n            if (nail[mid][0] < startPlank)\n                min = mid + 1;\n            else if (nail[mid][0] > endPlank)\n                max = mid - 1;\n            else {\n                max = mid - 1;\n                minIndex = mid;\n            }\n        }\n        if (minIndex == -1)\n            return -1;\n        int minIndexOrigin = nail[minIndex][1];\n        //find the smallest original position of nail that can nail the plank\n        for (int i = minIndex; i < nail.length; i++) {\n            if (nail[i][0] > endPlank)\n                break;\n            minIndexOrigin = Math.min(minIndexOrigin, nail[i][1]);\n            // we need the maximal index of nails to nail every plank, so the\n            // smaller index can be omitted    ****\n            if (minIndexOrigin <= preIndex) // ****\n                return preIndex;            // ****\n        } \n        return minIndexOrigin;\n    }\n}\n

\n\n

我不明白****解决方案中标有 , 的第 99-102 行。

\n\n

我的问题是：

\n\n

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

\n\n

解决方案有一点错误吗？

\n

Answer 1

这些行中处理的情况是，当您发现有一个索引可以钉住当前的木板时，该索引小于（或等于）我们需要能够钉住另一个（之前分析过的）木板的最低索引。在这种情况下，我们不需要进一步寻找当前的 plank，因为我们知道：

• 我们可以钉木板
• 我们可以使用不大于我们真正需要用于另一个 Plank 的索引的索引。

由于我们只对不同木板所需的最少索引中最大的索引（即“最差”木板的索引）感兴趣，因此我们知道我们现在刚刚找到的索引不再重要：如果我们已经知道我们将使用至少 的所有钉子preIndex，我们知道该组钉子中的一颗钉子将钉住当前的木板。我们可以退出循环并返回一个不会影响结果的“虚拟”索引。

注意调用循环中的效果：

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

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

您可以将其与 alpha-beta 剪枝进行比较。