Hi. 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 :(.

https://www.amazon.com/Algorithm-Design-Jon-Kleinberg/dp/0321295358

Chapter 4. Greedy Algorithms

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