Advertisement
iskhakovt

Untitled

Nov 19th, 2014
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.02 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. int main() {
  8.     int m, left, right, maxRight = 0, pos = 0;
  9.     cin >> m;
  10.  
  11.     vector <pair <int, int> > segs, answer;
  12.     while (cin >> left >> right) {
  13.         segs.push_back(make_pair(left, right));
  14.     }
  15.  
  16.     sort(segs.begin(), segs.end());
  17.  
  18.     while (maxRight < m) {
  19.         int currLeft, currRight = maxRight;
  20.  
  21.         while (pos != segs.size() && segs[pos].first <= maxRight) {
  22.             if (currRight < segs[pos].second) {
  23.                 currLeft = segs[pos].first;
  24.                 currRight = segs[pos].second;
  25.             }
  26.             ++pos;
  27.         }
  28.  
  29.         if (currRight == maxRight) {
  30.             cout << "No solution\n";
  31.             return 0;
  32.         }
  33.  
  34.         answer.push_back(make_pair(currLeft, currRight));
  35.         maxRight = currRight;
  36.     }
  37.  
  38.     cout << answer.size() << '\n';
  39.     for (auto const &i : answer) {
  40.         cout << i.first << ' ' << i.second << '\n';
  41.     }
  42.  
  43.     return 0;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement