P1668 [USACO04DEC] Cleaning Shifts S

There are $T(1\le T\le 10^6)$ time slots in a day. John plans to schedule his $N(1\le N\le 2.5\times 10^4)$ cows to be on duty to clean the barn. Each cow has her own available interval $ [S_i,E_i](1\le S_i\le E_i\le T)$ and only cows who are free can be scheduled. Moreover, every time slot must have a cow on duty. What is the minimum number of cows required to cover all time slots? If it is impossible to make a valid schedule, output $-1$.

The first line: $N$, $T$. Lines $2$ to $N+1$: $S_i$, $E_i$.

One line, output the minimum number of cows.

$1\le T\le 10^6$，$N\le 2.5\times 10^4$，$1\le S_i\le E_i\le T$。 $\text{Update On 2023/08/08}$：Added a set of hack testdata, see details [here](https://www.luogu.com.cn/discuss/613052). Ruled out wrong solutions with time complexity $\mathcal O(nt)$. Translated by ChatGPT 5