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
Intervals
Moderator: Board moderators
Re: Intervals
Sort the intervals according to their endpoint. [This is THE dirty trick. There are lots of similar problems where it can be appliedMek 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
]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
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
Understanding a problem in a natural way will lead to a natural solution
Read the parent post more carefully.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
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.
