Can Someone give me the proof of correctness for greedy aproach.
for the following test case
(1 100)
(4 8)
(4 15)
(35 43)
(42 55)
if by a single bomb placed at any point in 1 to 100 whole kingdom from 1 to 100 is destroyed .
then wont automatically whole kingdoms lying in range 1 to 100 destroyed?
Just sorted the intervals by right end and always placed a bomb at right end if the current interval cannot be destroyed by immediately previous bomb 
my solution
Exactly similar to this spoj problem.
1 Like
i used a similar activity selector algorithm given in cormen… but i got wrong answer…
here is the link to my solution CodeChef: Practical coding for everyone
plz explain why this algorithm can’t be implemented…
The problem , is the same as ZCO 2015 . Pasted the same solution, in nlogn .Got 100 .
1 Like
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.
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?
Setter and tester’s solution link showing access denied.
According to editorialist’s answer it will be available a little later (as I understood for all problems).
Can you explain your approach? 
I added it in meanwhile…
I too used a similar approach with O(N*log(N)) solution.
-
Sorted the intervals with start time.
-
Pushed first interval in stack.
-
From 2nd interval onwards i checked if intersects with the interval on top of stack ,if it does i need to push only the intersection.Otherwise push the new interval too.
-
Total no of intervals on stack is the number of bombs.
4 Likes
I also used similar approach with sorting by start time, only counted the number of bombs downwards.
Maybe I missed something, but you have several intervals on stack, how can you check only with first one?
Let say intervals are [1, 3], [2, 4], [5, 7] and [6, 8], stack processing 3 intervals is [2, 3], [5, 7]. Can you describe better what are you doing with last interval?