|
|
back to boardHi. I wonder, how can I solve it with dp? I thinked a whole day and cant find the solution less than O(N*T). Give me please some hint.
Just sort by endtime and use greedy. It's that easy. Why does it work? Can you prove that approach? I don't understand why it does work :(. O(N * T)? What is 'T'?
This can be solved using greedy, but the O(N^2) DP solution is as follows:
1) Sort by start times
dp[i]: maximum events that can be attended
iterate from j = 0 to i-1, if end time of j-th conference is less than start time of i-th and dp[j] + 1 > dp[i] then dp[i] = dp[j] + 1
answer is max of all elements of dp array You should save dp[max(end_time)]; remember that for each end time there maybe different start times so that (end - start) are different. Save these segments, mp[end].push_back(end-start + 1); now check from 1 to max(end_time) and for each i, if i is end time? then check this segments sizes, for each such segment dp[i] = 1 + dp[i - s]; where s is saved segment sizes for end time 'i'. https://pastebin.com/C3dagNL2 Edited by author 30.04.2022 18:18 |
|
|
