4eyes4u

Interval scheduling

Mar 28th, 2016
161
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.72 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N=2e5+10;
  5.  
  6. struct Interval
  7. {
  8.     int l, r;
  9.     friend bool operator<(const Interval& p, const Interval& q)
  10.     {
  11.         if (p.r==q.r) return p.l>q.l;
  12.         return p.r<q.r;
  13.     }
  14. } seg[N];
  15.  
  16. int n;
  17.  
  18. int schedule ()
  19. {
  20.     int ret=1, idx=0;
  21.     sort (seg, seg+n);
  22.  
  23.     for (int i=1;i<n;i++)
  24.     {
  25.         if (seg[i].l>=seg[idx].r)
  26.         {
  27.             idx=i;
  28.             ret++;
  29.         }
  30.     }
  31.  
  32.     return ret;
  33. }
  34.  
  35. int main()
  36. {
  37.     scanf ("%d", &n);
  38.     for (int i=0;i<n;i++)
  39.     {
  40.         int x, w;
  41.         scanf ("%d%d", &x, &w);
  42.         seg[i].l=x-w;
  43.         seg[i].r=x+w;
  44.     }
  45.  
  46.     printf ("%d", schedule());
  47.  
  48.     return 0;
  49. }
Advertisement
Add Comment
Please, Sign In to add comment