Selfish Grazing

Each of Farmer John's $N$ cows ($1 \le N \le 50000$) likes to graze in a certain part of the pasture, which can be thought of as one large one-dimensional number line. Cow $i$'s favorite grazing range starts at location $S_i$ and ends at location $E_i$ ($1 \le S_i < E_i \le 100000000$).

The cows are quite selfish: no cow wants to share any of its grazing area with another. Thus, two cows $i$ and $j$ can graze at the same time only if $S_i \ge E_j$ or $E_i \le S_j$. In other words, their ranges may touch at an endpoint but must not overlap. Farmer John would like to know the maximum number of cows that can graze at the same time, given the cows and their preferences.

Consider a set of 5 cows with the ranges shown below.

  ... 1    2    3    4    5    6    7    8    9   10   11   12   13 ...
  ... |----|----|----|----|----|----|----|----|----|----|----|----|----
Cow 1:      <===:===>          :              :              :
Cow 2: <========:==============:==============:=============>:
Cow 3:          :     <====>   :              :              :
Cow 4:          :              :     <========:===>          :
Cow 5:          :              :     <==>     :              :

These ranges represent $(2, 4)$, $(1, 12)$, $(4, 5)$, $(7, 10)$, and $(7, 8)$, respectively.

In one solution, the first, third, and fourth (or fifth) cows can all graze at the same time. If the second cow grazed, no other cow could graze. Also, the fourth and fifth cows cannot graze together, so it is impossible for four or more cows to graze.

• Line 1: A single integer $N$.
• Lines 2..N+1: Line $i+1$ contains two space-separated integers $S_i$ and $E_i$.

• Line 1: A single integer representing the maximum number of cows that can graze at once.