The problem , is the same as ZCO 2015 . Pasted the same solution, in nlogn .Got 100 .
1 Like
I understand your logic. I was thinking the same way at first.
But, A kingdom of the form [L, R] can be destroyed completely by placing a bomb at a point x on the real line if L ≤ x ≤ R. means, there has to be a bomb placed inside [L, R] for it to be destroyed. As long as a bomb is not placed between L and R, both inclusive, that kingdom cannot be destroyed.
The problem statement doesn’t say that if that kingdom completely falls within another that is destroyed, this also gets destroyed. (Unfortunately, … represented as intervals on the real line … makes it confusing. 
)
if we sort set according to start time
@darkshadows I have a question regarding your approach. I think I dont have permission to comment, so added as a answer. Why is sorting necessary before any operation in your approach? The one we are using to calculate the answer is ar[] and the values in it should be same irrespective of the sorting. Please mention the mistake in my approach because i observed that the solution is not accepted when i did not sort and is accepted when i sorted the array.
3
1 3
2 2
3 4
(Answer:2)
In the above test case if I placed the bomb on positon 3, won’t it destory all the locations?
So only one bomb required.
why the accpeted answer is 2?
“EXPLANATION:
First we sort all intervals according to increasing Bi.
Now, let’s say we have placed a bomb at position x on the line. All intervals such that their starting point Ai ≤ x will get destroyed. So we’ll greedily place the bombs when required.”
Clearly, this explanation is wrong. All intervals with Ai <= x AND x <= Bi will get destroyed. Just having the starting point less than x is not enough. Consider the example
Let {[1, 2], [3, 4], [5, 6], [7, 8]} be the intervals. As we can see they are sorted by increasing Bi. if we choose x = 7, the none of the intervals [1, 2], [3, 4], [5, 6] will be destroyed even though they satisfy Ai <= x.
in the above case how many bombs are required i think 1.
Someone please throw lights on the necessity of sorting the array according to ending time.A counter example will be enough.
Hello everyone ,there is no need of sorting here you can implement the above code without sorting.
here is my solution:
https://www.codechef.com/viewsolution/14315810
Why is this solution wrong – sorting the intervals based on Ai (start time), overlapping them, and then count the disjoint intervals?