STANAANDREY

coveredInter

Dec 15th, 2020 (edited)
282
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.86 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3. #define NMAX 1000
  4. struct Interval {
  5.     int a, b;
  6. } v[NMAX];
  7. int n;
  8.  
  9. void read() {
  10.     cin >> n;
  11.     for (int i = 1; i <= n; i++)
  12.         cin >> v[i].a >> v[i].b;
  13. }
  14.  
  15. void sort() {
  16.     for (int i = 1; i < n; i++)
  17.         for (int j = i + 1; j <= n; j++)
  18.             if (v[i].a > v[j].a)
  19.                 swap(v[i], v[j]);
  20.             else if (v[i].a == v[j].a && v[i].b < v[j].b)
  21.                 swap (v[i], v[j]);
  22. }
  23.  
  24. void greedy() {
  25.     int b = 0, r = 0;
  26.     for (int i = 1; i <= n; i++) {
  27.         if (b < v[i].a) {
  28.             b = v[i].b;
  29.             r++;
  30.         } else if (b >= v[i].a) {
  31.             if (b < v[i].b) {
  32.                 b = v[i].b;
  33.                 r++;
  34.             }
  35.         }
  36.     }
  37.     cout << n - r << endl;
  38. }
  39.  
  40. int main() {
  41.     read();
  42.     sort();
  43.     greedy();
  44.     return 0;
  45. }
  46.  
Add Comment
Please, Sign In to add comment