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)
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
Can any one please explain what is wrong in this solution.
Am trying to find a point which is contained in maximum number of intervals.
After finding such point, all the intervals which do not contain this point are preserved and which contain this point are removed from the intervallist[].
//intervallist[i].s //start of interval i
//intervallist[i].e //end of interval i
int bomb = 0;
while(totalintervals > 0)
{
bomb += 1;
memset(ab, 0, sizeof(ab));
for(i = 0; i < totalintervals; ++i)
{
ab[intervallist[i].s] += 1;
ab[intervallist[i].e+1] -= 1;
}
for(i = 1; i <= 2000; ++i)
{
ab[i] += ab[i-1];
}
//find the point which is contained in maximum number of intervals.
int max = -1;
int maxi = 0;
for(i = 0; i <= 2000; ++i)
{
if(ab[i] > max)
{
max = ab[i];
maxi = i;
}
}
// now all the intervals which do not contain the point(maxi) are preserved.
max = 0;
for(i = 0; i < totalintervals; ++i)
{
if((intervallist[i].s > maxi) || (maxi > intervallist[i].e))
{
intervallist[max] = intervallist[i];
max++;
}
}
totalintervals = max;
}
printf("%d\n", bomb);
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
i used a similar activity selector algorithm given in cormen… but i got wrong answer…
here is the link to my solution http://www.codechef.com/viewsolution/5754242
plz explain why this algorithm can’t be implemented…
@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.
