7_NailingPlanks

// you can use includes, for example:
#include <algorithm>
using namespace std;
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define g0( a ) get<0>( a )
#define g1( a ) get<1>( a )

int solution1(vector<int> &A, vector<int> &B, vector<int> &C) {
    // write your code in C++11 (g++ 4.8.2)
    auto max_index = -2;

    // Sorted value array sortC
    auto sortC = vii();
    for (int i = 0; i < C.size(); i++) {
        sortC.emplace_back(i, C[i]);
    }

    sort(sortC.begin(), sortC.end(), [](pii a, pii b) {
        return g1(a) < g1(b) || g1(a) == g1(b) && g0(a) < g0(b);
    });

    for (int i = 0; i < A.size(); i++) {
        auto a = A[i];
        auto b = B[i];
        auto it = lower_bound(sortC.begin(), sortC.end(), a,
                  [](pii ele, int a) { return g1(ele) < a; });

        if (it != sortC.end()) {
            auto lowest_pos = it;
            while (++it != sortC.end()) {
                if (g1(*it) >= a && g1(*it) <= b) {
                    if (g0(*lowest_pos) > g0(*it)) {
                        lowest_pos = it;
                    }

                    if (g0(*lowest_pos) < max_index) {
                        break;
                    }
                }
                else {
                    break;
                }
            }

            if (g1(*lowest_pos) >= a && g1(*lowest_pos) <= b) {
                if (max_index < g0(*lowest_pos)) {
                    max_index = g0(*lowest_pos);
                }
            }
            else {
                max_index = -2;
                break;
            }
        }
        else {
            max_index = -2;
            break;
        }
    }
    
    return max_index + 1;
}

int solution(vector<int> &A, vector<int> &B, vector<int> &C) {
    // write your code in C++11 (g++ 4.8.2)
    auto max_index = -2;

    auto ab = vii();
    for (int i = 0; i < A.size(); i++) {
        ab.emplace_back(A[i], B[i]);
    }
    sort(ab.begin(), ab.end(), [](pii a, pii b) {
        return g0(a) < g0(b) || (g0(a) == g0(b) && g1(a) < g1(b));
    });
    
    // Sorted value array sortC
    auto sortC = vii();
    for (int i = 0; i < C.size(); i++) {
        sortC.emplace_back(i, C[i]);
    }

    sort(sortC.begin(), sortC.end(), [](pii a, pii b) {
        return g1(a) < g1(b) || (g1(a) == g1(b) && g0(a) < g0(b));
    });

    auto firstC = sortC.begin();
    for (int i = 0; i < ab.size(); i++) {
        auto a = g0(ab[i]);
        auto b = g1(ab[i]);

        // Find the first nail met the condition
        while (firstC != sortC.end()) {
            if (g1(*firstC) >= a) break;
            firstC++;
        }

        // Not found
        if (firstC == sortC.end() || g1(*firstC) > b) { max_index = -2; break; }

        // Find the lowest index
        auto tempIt = firstC;
        auto lowest = firstC;
        while (tempIt != sortC.end()) {
            if (g1(*tempIt) >= a && g1(*tempIt) <= b && max_index < g0(*lowest)) {
                if (g0(*tempIt) < g0(*lowest)) {
                    lowest = tempIt;
                }
            }
            else {
                break;
            }

            tempIt++;
        }

        // Update largest nails to use
        if (max_index < g0(*lowest)) {
            max_index = g0(*lowest);
        }
        
        // // Update the iterator for performance
        // if (i != ab.size() - 1 && g1(*lowest) < g1(ab[i+1])) {
            // firstC = lowest;
        // }
    }

    return max_index + 1;
}