Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- we have 2 options for giving a exam whether we can give the exam on ai-th day or b-ith day.
- here we have to moove greedily. like sort the values in non-decreasing order of ai. because
- we have to give the exam in such a way so that our ai-should be in increasing order.
- and for a subject to choose we will be choosing bi only when if we choose bi and because of
- that choosing, the corresponding ai which is going to be listed on the record shoul be arranged
- in non decreasing manner other wise we will be choosing ai.
- given that ai > bi means as we have sorted ai so previous bi i.e. bi-1 will also be
- less than current ai as we have sorted.
- int ans = t[0][1]; // for the first subject we are choosing greedily the lowest day number
- for (int i = 1; i < n; ++i) {
- int schedule = t[i][0];
- int attendable = t[i][1];
- // making the i-th schedule, which will be listed, in non decreasing order.
- if (ans <= attendable) ans = attendable;
- else ans = schedule;
- }
- input:
- 3
- 3 2
- 5 1
- 6 4
- output:
- 6
- initially list is empty. i.e. []
- for the first subject we are choosing to give exam in 2nd day greedily. and list becomes [3].
- for the second if we choose to give exam on 1st day then list will be [5, 3] which is not a non-decreasing
- sequence to make this non decreasing we have to give second subject exam on day 5 and list will be [3, 5]
- which is non decreasing. and now for the 3rd subject if we choose to give exam on 4-th day list will be
- [3,6,5] which is again non decreasing because we have given the second subject's exam on day 5 so to make
- the whole list increasing we have to give exam of 3rd subject on day 6 and list will become [3, 5, 6].
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement