Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <set>
- bool checkAllNailed(const vector<pair<int, int>>& planks, const vector<int>& nails) {
- int p = 0;
- set<pair<int, int>> open;
- for (const int nail : nails) {
- while (p < planks.size() && planks[p].first <= nail) {
- open.insert(make_pair(planks[p].second, planks[p].first));
- p++;
- }
- while (!open.empty() && (*open.begin()).first >= nail) {
- open.erase(open.begin());
- }
- }
- return open.empty() && (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;
- vector<int> nails;
- for (int i = 0; i <= m; i++) {
- nails.push_back(C[i]);
- }
- sort(nails.begin(), nails.end());
- bool solves = checkAllNailed(planks, nails);
- if (solves) {
- e = m;
- } else {
- s = m + 1;
- }
- }
- return s + 1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement