E. A29 贪心算法【思维】最多无相交线段数 [USACO09DEC] Selfish Grazing S

传统题

1000ms

512MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题目描述】

数轴上有 $n$ 条线段，每条线段的两个端点坐标为 $a_i$ 和 $b_i$ 。

选取若干条线段，要求所选线段两两不相交（端点重合不算），求最多能选多少条线段？

第一行一个正整数 $n \ (1 \le n \leq 10^6)$ 。

下来 $n$ 行，每行两个数 $a_i \ b_i$ （ $0 \leq a_i \lt b_i \leq 10^9$ ）。

一行一个整数，即能选取的线段数的最大值。