# L14-NailingPlanks
###### tags: `Codility_lessons`
## Question
https://app.codility.com/programmers/lessons/14-binary_search_algorithm/nailing_planks/
## Key
1. 要釘幾個釘子才能將板子牢固，用二分搜尋找釘子數目mid =( 0 + C.size())/2

2. 問題是要怎麼確認釘子符合A[k] <= C[i]<= B[k]，第一個方法兩個while loop，才能在不符合時，讓C移動到下一個再試一次

3. 第二個方法是類似prefix sum，利用一個陣列將所有C[i]出現過的點都記錄為1，並進行壘加，如果在A[K]和B[k]的位置間有C[i]出現，那麼陣列在位置B[k]和A[k]-1的累加值不會一樣，反之，會一樣，此時舅就要換下一個C[i]進行嘗試，假設到mid還不符合，代表釘子數目太小，要增加

## Reference
## Solution

### Sol. I

def check(A, B, C, K):
    # sort the nails if the positions are random
    C.sort()
    C_len = len(C)
    A_len = len(A)
    i = 0
    j = 0
    while K > 0 and i < C_len:
        while j < A_len:
            if A[j] <= C[i] <= B[j]:
                j += 1
            else:
                break
        K -= 1
        i += 1
    if K < 0 or j < A_len:
        return False
    else:
        return True

### Sol. II

bool nailed(vector<int>& A, vector<int>& B, vector<int>& C, int maxNails) {
    int n = A.size();
    int m = C.size();
    vector<int> nailsCounter(m * 2 + 1, 0);
    for (int i = 0; i < maxNails; ++i) {
        nailsCounter[C[i]] = 1;
    }
    int counter = 0;
    for (auto &v: nailsCounter) {
        counter += v;
        v = counter;
    }
    for (int i = 0; i < n; ++i) {
        if (nailsCounter[A[i] - 1] == nailsCounter[B[i]]) return false;
    }
    return true;
}
int solution(vector<int>& A, vector<int>& B, vector<int>& C) {
    int lower = 1, upper = C.size();
    if (!nailed(A, B, C, upper)) return -1;
    while (lower < upper) {
        int nails = (lower + upper) / 2;
        if (nailed(A, B, C, nails)) upper = nails;
        else lower = nails + 1;
    }
    return lower;
}