P7391 "TOCO Round 1" Adaptive PVZ

After finishing today’s tricky 3D computational geometry, $\color{black}\texttt{Q}\color{red}\texttt{wQcOrZ}$ opened an interesting exe file.

The unlucky $\color{black}\texttt Q\color{red}\texttt{wQcOrZ}$ encountered $n$ zombies on the lawn. Zombie $i$ appears at time $l_i$ and will enter the house at time $r_i$. $\color{black}\texttt Q\color{red}\texttt{wQcOrZ}$ has $m$ Peashooters. If a Peashooter keeps attacking zombie $i$ continuously during the time interval from $l_i$ to $r_i$ (excluding both endpoints), then it can kill zombie $i$. However, during the attack it cannot attack any other zombie, and the target zombie cannot be changed. Now $\color{black}\texttt Q\color{red}\texttt{wQcOrZ}$ wants to know: with a proper schedule, what is the minimum number of zombies that will enter his house.

The first line contains two integers $n, m$, representing the number of zombies and the number of Peashooters. The next $n$ lines each contain two integers $l_i$ and $r_i$, representing the time when zombie $i$ appears and the time when it enters the house.

Output one integer representing the answer.

For $30\%$ of the testdata, $n, m \leq 6$. For $60\%$ of the testdata, $n, m \leq 10^3$. For another $20\%$ of the testdata, $m \geq n$. For $100\%$ of the testdata, $1 \leq n, m \leq 2 \times 10^5$, $1 \leq l_i < r_i \leq 10^9$. Translated by ChatGPT 5