Codility Nailing木板

Question

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

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

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

Link 解决方案： 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 没有钉住当前的木板怎么办？

是不是解法有点错误？

Answer 1

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

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

由于我们只对不同木板所需的最少索引中的最大索引感兴趣（即 "worst" 木板的索引），我们知道我们现在找到的索引并不重要any more：如果我们已经知道我们将至少使用所有钉子 preIndex，我们就知道该组中的一个钉子将钉住当前的木板。我们可以退出循环并 return 一个不会影响结果的 "dummy" 索引。

注意调用循环中的效果：

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

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

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

Answer 2

https://app.codility.com/demo/results/trainingR7UKQB-9AQ/

这是 100% 的解决方案。木板被压缩成 (begin, end) 对并排序，支持二进制搜索。对于每个钉子，该钉子用于在搜索失败之前移除尽可能多的木板。当木板数组为空时，可以返回当前钉子的索引，表示使用的钉数。

O((N + M) * log(M))

所有代码都在这里，https://github.com/niall-oc/things/blob/master/codility/nailing_planks.py

def find_plank(nail, planks):
    """
    planks is an array of pairs (begin, end) for each plank.
    planks is sorted by start position of planks
    """
    if not planks:
        return -1 # empty planks
    BEGIN_IDX = 0
    END_IDX = 1
    lower = 0
    upper = len(planks)-1
    while lower <= upper:
        mid = (lower + upper) // 2
        if planks[mid][BEGIN_IDX] > nail:
            upper = mid - 1
        elif planks[mid][END_IDX] < nail:
            lower = mid + 1
        else: # nail hits plank[mid]
            return mid # return this plank id so we can pop the plank
    return -1


def solution(A, B, C):
    """
    Strategy is to sort the planks first. Then scan the nails and do the following.
    For each nail perform a binary search for a plank.
        if plank found then pop plank then search again until the nail hits no more planks.
    The plank list should diminish until it hits zero meaning we have found the minimum number of nails needed
    If any planks remain then return -1

    100% https://app.codility.com/demo/results/trainingR7UKQB-9AQ/
    """

    if max(B) < min(C) or max(C) < min(A):
        return -1 # no nail can hit that plank

    planks = sorted(zip(A,B))

    for i in range(len(C)):
        nail = C[i]
        p_idx = find_plank(nail, planks)
        # print(f'idx{i} nail at pos {nail}, matched {p_idx}, in {planks}')
        while p_idx > -1:
            del planks[p_idx]
            p_idx = find_plank(nail, planks)
            # print(f'idx{i} nail at pos {nail}, matched {p_idx}, in {planks}')
        if not planks:
            # print('NO PLANKS', i+1)
            return i+1 # the index of the nail that removed the last plank.

    return -1 # else we couldn't remove all planks

Answer 3

这是整个算法的总结。我想谁看懂了，心里就不会有疑问了。

我们在做什么？

1- 在不丢失原始索引的情况下订购指甲。

2-对于每块木板，使用二分查找找到可以钉木板的最小钉值。

3- 求每个钉子在最小钉值和木板末端位置之间的最小原始索引，取这些最小原始索引中的最小值。

4-Return每块木板最小钉原指数的最大值

我们为什么要这样做？

1- 我们不想搜索整个数组来找到最小索引。索引的原始顺序就是要求的，所以我们需要存储它。

2-我们需要找到最小的钉值来限制可能需要检查的原始索引的数量。需要二分查找以对数时间复杂度找到最小值。

3-我们需要找到候选指甲的原始索引。第一个候选可以是最小钉值，最后一个候选可以是木板的终点位置。这就是为什么我们只在这个时间间隔检查原始索引。

4- 我们找到每块木板的最小原始钉子索引。但是答案将是这些最小索引中的最大值，因为问题询问我们使用的最后一个钉子的索引，当我们钉完每块木板时。

Answer 4

我想针对所需的 O(log(M) * (M + N)) 运行时复杂度提供我的算法和实现。

对 C 元素进行二进制搜索。
对于每次迭代，创建一个前缀总和来确定当前的二分搜索迭代。这将需要两个步骤：
一种。统计C中指甲位置的出现次数。
b.为特定索引处的可用钉子创建适当的前缀和。
如果木板范围内没有钉子，那么那里找不到钉子，因此无法解决该任务。
如果那个连续的数组没有解，我们需要寻找更长的范围。
如果在那个连续序列中有解，我们需要寻找更小的范围。
继续二分搜索，直到我们最终找到最小范围。

二分搜索的运行时复杂度为log(M)，因为我们将 M 的范围一分为二。内部迭代的运行时复杂度来自三个循环：

一个。 O(mid)，其中 mid < M。所以，这是最坏情况下的O(M)。
b. O(2M)，即 O(M)，因为我们可以保留常量。
C。 O(N)，遍历A和B中的元素个数

因此，内循环的运行时复杂度为O(M + N)。

因此算法的总体运行时复杂度为 O(log(M) * (M + N))。

前缀总和的总体 space 复杂度为 O(2 * M)，因此基本上 O(M)。

bool check(vector<int> &A, vector<int> &B, vector<int> &C, int mid)             
{                                                                               
  const int M = C.size();                                                       
  vector<int> prefix_sums(2 * M + 1, 0);                                        
  for (int i = 0; i < mid; ++i) ++prefix_sums[C[i]];                            
  for (size_t i = 1; i < prefix_sums.size(); ++i) prefix_sums[i] += prefix_sums[i - 1];
  for (size_t i = 0; i < A.size(); ++i) if (prefix_sums[B[i]] == prefix_sums[A[i] - 1]) return false;
  return true;                                                                  
}

int solution(vector<int> &A, vector<int> &B, vector<int> &C)                    
{                                                                               
  int start = 1;                                                                
  int end = C.size();                                                           
  int min_nails = -1;                                                           
  while (start <= end) {                                                        
    int mid = (start + end) / 2;                                                
    if (check(A, B, C, mid)) { end = mid - 1; min_nails = mid; }                
    else start = mid + 1;                                                       
  }                                                                             
  return min_nails;                                                             
}

Codility Nailing木板

Codility NailingPlanks

java

algorithm

binary-search