P2970 [USACO09DEC] Selfish Grazing S

Each of Farmer John’s $N$ cows ($1 \le N \le 50{,}000$) likes to graze in a specific part of the pasture, which can be modeled as a 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 100{,}000{,}000$). 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$. Farmer John would like to know the maximum number of cows that can graze at the same time for a given set of cows and their preferences. Consider a set of 5 cows with ranges shown below: ```cpp ... 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. As a solution, the first, third, and fourth (or fifth) cows can all graze at the same time. If the second cow grazed, no other cows 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.

Translated by ChatGPT 5