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.
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.
n,a,b = input ar= //ar* denotes maximum starting point for intervals ending at i for i=1 to N: ar[b*]=max(ar[b*], a*) 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*: ans += 1 max = i print ans