[978G-Petya's Exam](http://mirror.codeforces.com/contest/978/problem/G)↵
----------------------------------------------------------------↵
1. This is a greedy problem. First thing to notice is that exam which is occurring earlier compared to others should be prepared first, i.e. exam which is having less $d_i$ should be prepared earlier(if value of $s$ allows to do so). ↵
↵
2. Sort the exams in the increasing order of $d_i$. If we go through solution we can see that it gives optimum solution. ↵
↵
3. Let us take an exam from the sorted order = {$s_i$ , $d_i$, $c_i$}. Since we have sorted exams $\implies$, $1\leq$$j$$\leq$$n$ AND $j$$\neq$$i$; either $d_i$$\leq$$d_j$ or $j^{th}$ exam is completed(We are processing in increasing order of $d_i$). Now we have to prepare $c_i$ days for exam $i$ in the interval $s_i$ and $d_i$(and obviously we are forced to do so, so that's an optimal step). Now since all other exams(for which preparation is not done yet) are after $i^{th}$ exam, **what is the best way to choose $c_i$ days in the interval $[s_{i},d_{i}]$ such that we leave better opportunities for the preparation of other exams**?If we iterate from $s_i$ to $d_i$ and choose first $c_i$ days which are free for preparation. Hence our solution is optimal. ↵
↵
4. Worst case time complexity is : O(m*n).↵
----------------------------------------------------------------↵
1. This is a greedy problem. First thing to notice is that exam which is occurring earlier compared to others should be prepared first, i.e. exam which is having less $d_i$ should be prepared earlier(if value of $s$ allows to do so). ↵
↵
2. Sort the exams in the increasing order of $d_i$. If we go through solution we can see that it gives optimum solution. ↵
↵
3. Let us take an exam from the sorted order = {$s_i$ , $d_i$, $c_i$}. Since we have sorted exams $\implies$, $1\leq$$j$$\leq$$n$ AND $j$$\neq$$i$; either $d_i$$\leq$$d_j$ or $j^{th}$ exam is completed(We are processing in increasing order of $d_i$). Now we have to prepare $c_i$ days for exam $i$ in the interval $s_i$ and $d_i$(and obviously we are forced to do so, so that's an optimal step). Now since all other exams(for which preparation is not done yet) are after $i^{th}$ exam, **what is the best way to choose $c_i$ days in the interval $[s_{i},d_{i}]$ such that we leave better opportunities for the preparation of other exams**?If we iterate from $s_i$ to $d_i$ and choose first $c_i$ days which are free for preparation. Hence our solution is optimal. ↵
↵
4. Worst case time complexity is : O(m*n).↵
