Guest User

Untitled

a guest
Dec 5th, 2014
540
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <functional>
  4.  
  5. using namespace std;
  6.  
  7.  
  8. struct exam
  9. {
  10.     int starttime;
  11.     int endtime;
  12. };
  13.  
  14.  
  15. bool examcompare(exam lhs, exam rhs)
  16. {
  17.     return lhs.starttime<rhs.starttime;
  18. };
  19.  
  20. int main()
  21. {
  22.  
  23.     long long int counter=0, noofleave=0, noofreturn=0, noofexams=0, bestleave=0, bestreturn=0, trip=0, besttrip=99999999;
  24.  
  25.     cin>>noofexams>>noofleave>>noofreturn;
  26.  
  27.     long int leavearray[noofleave], returnarray[noofreturn];
  28.     exam examarray[noofexams];
  29.  
  30.  
  31.  
  32.     for(counter=0; counter<noofexams; counter++)
  33.     {
  34.         cin>>examarray[counter].starttime>>examarray[counter].endtime;
  35.     }
  36.  
  37.     for(counter=0; counter<noofleave; counter++)
  38.     {
  39.         cin>>leavearray[counter];
  40.     }
  41.  
  42.     for(counter=0; counter<noofreturn; counter++)
  43.     {
  44.         cin>>returnarray[counter];
  45.     }
  46.  
  47.  
  48.     sort(examarray, examarray+noofexams, examcompare);
  49.  
  50.     sort(leavearray, leavearray+noofleave);
  51.  
  52.     sort(returnarray, returnarray+noofreturn);
  53.  
  54.     long int low=0, high=0, mid=0;
  55.  
  56.     for(counter=0; counter<noofexams; counter++)
  57.     {
  58.         if(leavearray[0]>examarray[counter].starttime)
  59.         {
  60.             continue;
  61.         }
  62.  
  63.         else if(leavearray[noofleave-1]<=examarray[counter].starttime)
  64.         {
  65.             bestleave=leavearray[noofleave-1];
  66.         }
  67.  
  68.         else
  69.         {
  70.             low=0;
  71.             high=noofleave-1;
  72.  
  73.             while(low!=high)
  74.             {
  75.                 mid=(high+low)/2;
  76.  
  77.                 if(leavearray[mid]<=examarray[counter].starttime)
  78.                 {
  79.                     low=mid+1;
  80.                 }
  81.  
  82.                 else
  83.                 {
  84.                     high=mid;
  85.                 }
  86.  
  87.             }
  88.  
  89.             bestleave=leavearray[high-1];
  90.         }
  91.  
  92.         if(returnarray[noofreturn-1]<examarray[counter].endtime)
  93.         {
  94.             continue;
  95.         }
  96.  
  97.         else if(returnarray[noofreturn-1]==examarray[counter].endtime)
  98.         {
  99.             bestreturn=returnarray[noofreturn-1];
  100.         }
  101.  
  102.         else
  103.         {
  104.             low=0;
  105.             high=noofreturn-1;
  106.  
  107.             while(low!=high)
  108.             {
  109.                 mid=(high+low)/2;
  110.  
  111.                 if(returnarray[mid]<=examarray[counter].endtime)
  112.                 {
  113.                     low=mid+1;
  114.                 }
  115.  
  116.                 else
  117.                 {
  118.                     high=mid;
  119.                 }
  120.  
  121.             }
  122.  
  123.             if(returnarray[high-1]==examarray[counter].endtime)
  124.             {
  125.                 bestreturn=returnarray[high-1];
  126.             }
  127.  
  128.             else
  129.             {
  130.                 bestreturn=returnarray[high];
  131.             }
  132.  
  133.         }
  134.  
  135.         trip=(bestreturn-bestleave)+1;
  136.  
  137.         if(trip<besttrip)
  138.         {
  139.             besttrip=trip;
  140.         }
  141.  
  142.     }
  143.  
  144.  
  145. cout<<besttrip;
  146.  
  147.     return 0;
  148.     }
RAW Paste Data