Advertisement
Guest User

Untitled

a guest
Dec 11th, 2012
35
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.99 KB | None | 0 0
  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4.  
  5. struct interval
  6. {
  7. int in;
  8. int sf;
  9. };
  10.  
  11. bool cmp(interval a, interval b)
  12. {
  13. return a.in<b.in;
  14. }
  15.  
  16. interval v[1000];
  17.  
  18. int max(int a, int b)
  19. {
  20. if(a>b)return a;
  21. if(b>a)return b;
  22. return a;
  23. }
  24.  
  25. int main()
  26. {
  27. freopen("acoperire.in","r",stdin);
  28. freopen("acoperire.out","w",stdout);
  29. int st,dr,n;
  30. scanf("%d%d",&st,&dr); // capetele intervalului
  31. scanf("%d",&n); // nr intervale mici
  32. for(int i=1;i<=n;i++)
  33. scanf("%d%d",&v[i].in,&v[i].sf); // intervale mici
  34. int reper=st, departe=st-1,nr=1;
  35. sort(v+1,v+n+1,cmp);
  36. bool ok=0;
  37. for(int i=1;i<=n;i++)
  38. {
  39. if(v[i].in<=reper)
  40. departe=max(departe,v[i].sf);
  41. else
  42. if(v[i].in>departe)
  43. {
  44. printf("-1");
  45. ok=1;
  46. break;
  47. }
  48. else
  49. {
  50. nr++;
  51. reper=departe;
  52. departe=v[i].sf;
  53. }
  54. if(departe>=dr)
  55. break;
  56. }
  57. if(ok==0)
  58. if(v[n].sf<st)
  59. {
  60. printf("-1");
  61. ok=1;
  62. }
  63. if(ok==0)
  64. printf("%d",nr);
  65. return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement