OJ Board

Hi all !

Can somebody tell me how to solve this problem?

There are N intervals (ai, bi). ai and bi are integers not exceeding 2'000'000'000 by their absolute value.
Your task is to find the number of ways we could choose a maximal subset of disjoint intervals.
1 ≤ N ≤ 100000

Mek wrote:Hi all !

Can somebody tell me how to solve this problem?

There are N intervals (ai, bi). ai and bi are integers not exceeding 2'000'000'000 by their absolute value.
Your task is to find the number of ways we could choose a maximal subset of disjoint intervals.
1 ≤ N ≤ 100000

Sort the intervals according to their endpoint. [This is THE dirty trick. There are lots of similar problems where it can be applied ]

Use dynamic programming to determine the best solution (and the number of such solutions) for the first K intervals, where K goes from 1 to N.

why DP? Isn't this a greedy solution (after sorting the array):

1. set end = -2,000,000,000; count = 0;
2. go through the array and choose first elemen that has ai > end,
end = bi (of that element)
increase count

repeat step 2 until you've crossed the array, and count is your answer

jakabjr wrote:why DP? Isn't this a greedy solution (after sorting the array):

1. set end = -2,000,000,000; count = 0;
2. go through the array and choose first elemen that has ai > end,
end = bi (of that element)
increase count

repeat step 2 until you've crossed the array, and count is your answer

Read the parent post more carefully.

He doesn't want the size of the maximal subset of disjoint intervals (this could be solved by the greedy approach you mention).
He wants the number of different subsets having the largest possible size. In other words, we have to count all optimal solutions, not just find one of them. In this case the DP is necessary.

Can you help me with DP solution?

D[k] - is best solution for first K intervals

If I know D[1] ... D[k - 1]
How to express D[k] ?

D[1]= 1
...
for D[k] seek in D[k-1]..D[1] the first interval that has bi < ak
D[k] = D+1
if there is no such interval (i=0) D[k] = 1

I think i can't do this because time will be O(n^2) but I need faster

but this can be done by binary search and time will be O(n log n)
I will now try this...

I did it with O(n^2) ... but it's too slow... i can't understand how to do it in O(nlogn)