Advertisement
Guest User

Untitled

a guest
May 4th, 2015
198
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.93 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. struct section {
  6.     int start;
  7.     int end;
  8. };
  9.  
  10. bool cmp(const section& s1, const section& s2) {
  11.     return s1.start > s2.start;
  12. }
  13.  
  14. int main() {
  15.     std::vector<section> sects;
  16.     int n;
  17.     std::cin >> n;
  18.     for (int i = 0; i < n; ++i) {
  19.         section sect;
  20.         std::cin >> sect.start >> sect.end;
  21.         sects.push_back(sect);
  22.     }
  23.     std::sort(sects.begin(), sects.end(), cmp);
  24.     std::vector<section> res;
  25.     section s = sects.back();
  26.     sects.pop_back();
  27.  
  28.     while (!sects.empty()) {
  29.         section tmp = sects.back();
  30.         sects.pop_back();
  31.         if (tmp.start <= s.end) {
  32.             s.start = tmp.start;
  33.             s.end = std::min(s.end, tmp.end);
  34.         }
  35.         else {
  36.             res.push_back(s);
  37.             s = tmp;
  38.         }
  39.     }
  40.  
  41.     res.push_back(s);
  42.  
  43.     std::cout << res.size() << std::endl;
  44.     for (std::vector<section>::iterator it = res.begin(), end = res.end(); it != end; ++it) {
  45.         std::cout << it->start << std::endl;
  46.     }
  47.  
  48.     return 0;
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement