### PROBLEM LINK:

**Author:** Snigdha Chanda

**Tester:** Shiplu Hawlader

**Editorialist:** Lalit Kundu

### DIFFICULTY:

EASY-MEDIUM

### PRE-REQUISITES:

Greedy

### PROBLEM:

Given **N (≤100000)** intervals **[A _{i}, B_{i}]**, one such interval can be deleted by placing a bomb at

**x**if

**A**. Find minimum number of bombs required to delete all intervals.

_{i}≤ x ≤ B_{i}### EXPLANATION:

First we sort all intervals according to increasing **B _{i}**.

Now, let’s say we have placed a bomb at position

**x**on the line. All intervals such that their starting point

**A**will get destroyed. So we’ll greedily place the bombs when required.

_{i}≤ xPseudo code:

```
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
```

Complexity: **O(N+2000)**.