NailingPlanks

#include <algorithm>
#include <limits>
#include <set>

bool checkAllNailed(const vector<pair<int, int>>& planks, const vector<int> &C, int j) {
    vector<int> nails;
    for (int i = 0; i <= j; i++) {
        nails.push_back(C[i]);
    }
    sort(nails.begin(), nails.end());

    int p = 0;
    for (const int nail : nails) {
        while (p < planks.size() && planks[p].first <= nail) {
            if (planks[p].second < nail) {
                return false;
            }
            p++;
        }
    }
    return (p == planks.size());
}

int solution(vector<int> &A, vector<int> &B, vector<int> &C) {
    vector<pair<int, int>> planks;
    for (int i = 0; i < A.size(); i++) {
        planks.push_back(make_pair(A[i], B[i]));
    }
    sort(planks.begin(), planks.end());

    int s = 0;
    int e = C.size() - 1;
    while (s != e) {
        int m = (s + e) / 2;

        bool solves = checkAllNailed(planks, C, m);
        if (solves) {
            e = m;
        } else {
            s = m + 1;
        }
    }

    if (checkAllNailed(planks, C, s)) {
        return s + 1;
    }
    return -1;
}