Advertisement
Guest User

NailingPlanks

a guest
Mar 29th, 2020
241
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.23 KB | None | 0 0
  1. #include <algorithm>
  2. #include <set>
  3.  
  4. bool checkAllNailed(const vector<pair<int, int>>& planks, const vector<int>& nails) {
  5. int p = 0;
  6. set<pair<int, int>> open;
  7.  
  8. for (const int nail : nails) {
  9. while (p < planks.size() && planks[p].first <= nail) {
  10. open.insert(make_pair(planks[p].second, planks[p].first));
  11. p++;
  12. }
  13. while (!open.empty() && (*open.begin()).first >= nail) {
  14. open.erase(open.begin());
  15. }
  16. }
  17. return open.empty() && (p == planks.size());
  18. }
  19.  
  20. int solution(vector<int> &A, vector<int> &B, vector<int> &C) {
  21. vector<pair<int, int>> planks;
  22. for (int i = 0; i < A.size(); i++) {
  23. planks.push_back(make_pair(A[i], B[i]));
  24. }
  25. sort(planks.begin(), planks.end());
  26.  
  27. int s = 0;
  28. int e = C.size() - 1;
  29. while (s != e) {
  30. int m = (s + e) / 2;
  31.  
  32. vector<int> nails;
  33. for (int i = 0; i <= m; i++) {
  34. nails.push_back(C[i]);
  35. }
  36. sort(nails.begin(), nails.end());
  37.  
  38. bool solves = checkAllNailed(planks, nails);
  39. if (solves) {
  40. e = m;
  41. } else {
  42. s = m + 1;
  43. }
  44. }
  45. return s + 1;
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement