P1803 Messy yyy / Segment Coverage

Python users can try submitting with pypy3. NOIP is coming soon, and yyy is very nervous!

There are $n$ contests on various OJ sites, and the start and end times of each contest are known. yyy believes that the more contests he attends, the better he will do in NOIP (not really). So, he wants to know the maximum number of contests he can attend. Since yyy is a "juruo" (rookie), if he decides to attend a contest, he must see it through from start to finish, and he cannot attend $2$ or more contests at the same time.

The first line contains an integer $n$. The next $n$ lines each contain $2$ integers $a_{i},b_{i}\ (a_{i}

Output a single integer: the maximum number of contests he can attend.

- For $20\%$ of the testdata, $n \le 10$. - For $50\%$ of the testdata, $n \le 10^3$. - For $70\%$ of the testdata, $n \le 10^{5}$. - For $100\%$ of the testdata, $1\le n \le 10^{6}$, $0 \le a_{i} < b_{i} \le 10^6$. Translated by ChatGPT 5