Given N (≤100000) intervals [Ai, Bi], one such interval can be deleted by placing a bomb at x if Ai ≤ x ≤ Bi. Find minimum number of bombs required to delete all intervals.
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.
Pseudo code:
n,a,b = input
ar=[] //ar[i] denotes maximum starting point for intervals ending at i
for i=1 to N:
ar[b[i]]=max(ar[b[i]], a[i])
ans=0
max=-1 //denotes the latest value of x where we placed a bomb
for i=0 to 2000:
//we need a bomb to all intervals ending at i'th position
if max < ar[i]:
ans += 1
max = i
print ans
I spent a lot of time on this ones, getting TLE for O(2N * log(2N)) solution (both in Java and C++). I think this is not a problem if we had to solve it in O(N+2000) and then time limit was increased
With increased time limit the solution can be:
for earch interval add two events - interval start/end
sort events by coordinates if two events have same coordinate, start events are before end events
process all events - for start event insert interval index to set of opened intervals, on end event if interval index is in set of opened intervals add bomb and clear set of opened intervals (all are destroyed) if is not in set (because it was cleared before) do nothing (continue with next event)
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.
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?
after processing 3 intervals [5,7] will be on top of stack so i compare [5,7] with [6,8] they intersect so i pop [5,7] and push [6,7].
Finally stack contents are [2,3] [6,7]
I agree with you, first I got confused on how to do it under 0.50 seconds. I tried O(N) but got WA. I knew the code was wrong (it gave wrong answers in some test cases by me). Then when I saw time limit as 2 seconds, I got angry on the problem setter, as this means the question in nothing but reduced to an activity selection problem in which N*log(N) can be used. thus ACed today.
Why I am not able to see the Setter’s solution.
Showing:
This XML file does not appear to have any style information associated with it. The document tree is shown below.
I have a similar approach but slightly different. sort according to ending time. then have the answer as n(no. of intervals ). for each overlap subtract the answer by 1. got AC. MY SOLUTION
Hi. Can somebody tell me why my solution is wrong? I have implemented the same idea that is described here but I can’t find my mistake. Here is the link to my solution
