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

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

My DP solution works in ~0.001 seconds, please optimize your DP.

Thank you! This test helped me to fix WA6

Edited by author 10.07.2019 16:23

5
1 8
2 3
4 5
6 7
9 10

Answer: 4.

Try this:
3
1 5
2 5
3 5
Answer: 1

Why does this solution work? Can anybody prove that? I dont understand why it work. Thanks!

you can replace

for x in range(confs):
    l.append(tuple(map(int, input().split())))

by

for x in sys.stdin:
    l.append(tuple(map(int, x.strip().split())))

I don't think sorting by startTime is necessary. I think we should reverse-sort by startTime.

Thanks. This helped me.

Finally got accepted in Go
Used bufio instead of fmt. fmt is unbuffered and might be very slow

New tests were added. Read Site news.

thank you . you inspired me!

Thanks man!

This is Test 2:
7
1 90
91 125
129 200
3 130
140 150
160 162
201 202

The answer is 5.

Yes, thanks for the problem.
My solution is one sort, DP without recursion and with binary search.
AC since 19th try :)

i think this problem can be solved using greedy algo too,
sort them according to the ending time, take a time variable 't',we took the interval whose starting time is later than 't' and choose the one which ends the earliest.

for example: 1-4 4-14 6-10 3-7 11-16
sorted: 1-4 3-7 6-10 4-14 11-16
here 1-4 ends the earliest, then we have a choose 6-10 (as 3-7 starting time is before 4)
....
i think you get the idea.

Edited by author 11.11.2012 02:32

Me too. Who can help?