978G-Petya's Exam

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).

1. Sort the exams in the increasing order of d_i. If we go through solution we can see that it gives optimum solution.

2. Let us take an exam from the sorted order = {s_i , d_i, c_i}. Since we have sorted exams , 1 ≤ j ≤ n AND j ≠ 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.

Worst case time complexity is : O(m*n).