What is DP solution? Thx

Posted by

Dmitriy 21 Sep 2016 13:50

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.

Re: What is DP solution? Thx

Just sort by endtime and use greedy. It's that easy.

Re: What is DP solution? Thx

Posted by

Dmitriy 22 Sep 2016 05:41

Why does it work? Can you prove that approach? I don't understand why it does work :(.

Re: What is DP solution? Thx

Posted by

Egor 14 Nov 2016 14:08

Re: What is DP solution? Thx

Posted by

Aashir 1 Jan 2017 22:35

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