Advertisement
helloInfinity

exams activity selection

Sep 8th, 2022
215
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.65 KB | Software | 0 0
  1. we have 2 options for giving a exam whether we can give the exam on ai-th day or b-ith day.
  2. here we have to moove greedily. like sort the values in non-decreasing order of ai. because
  3. we have to give the exam in such a way so that our ai-should be in increasing order.
  4. and for a subject to choose we will be choosing bi only when if we choose bi and because of
  5. that choosing, the corresponding ai which is going to be listed on the record shoul be arranged
  6. in non decreasing manner other wise we will be choosing ai.
  7. given that ai > bi means as we have sorted ai so previous bi i.e. bi-1 will also be
  8. less than current ai as we have sorted.
  9.  
  10. int ans = t[0][1]; // for the first subject we are choosing greedily the lowest day number
  11.  
  12. for (int i = 1; i < n; ++i) {
  13.  
  14. int schedule = t[i][0];
  15. int attendable = t[i][1];
  16. // making the i-th schedule, which will be listed, in non decreasing order.
  17. if (ans <= attendable) ans = attendable;
  18. else ans = schedule;
  19. }
  20.  
  21. input:
  22. 3
  23. 3 2
  24. 5 1
  25. 6 4
  26. output:
  27. 6
  28.  
  29. initially list is empty. i.e. []
  30. for the first subject we are choosing to give exam in 2nd day greedily. and list becomes [3].
  31. for the second if we choose to give exam on 1st day then list will be [5, 3] which is not a non-decreasing
  32. sequence to make this non decreasing we have to give second subject exam on day 5 and list will be [3, 5]
  33. which is non decreasing. and now for the 3rd subject if we choose to give exam on 4-th day list will be
  34. [3,6,5] which is again non decreasing because we have given the second subject's exam on day 5 so to make
  35. the whole list increasing we have to give exam of 3rd subject on day 6 and list will become [3, 5, 6].
  36.  
  37.  
  38.  
  39.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement