不相交的区间

ID: 4390

传统题

1000ms

256MiB

难度: (无)

上传者:

标签>

贪心

问题描述

数轴上有 $n$ 个开区间 $(a_i, b_i)$ ，选择尽量多个区间，使得这些区间两两没有公共点。

第一行，输入一个整数 $n$ （ $n \leq 100000$ ），表示有 $n$ 个开区间。

第二行到第 $n+1$ 行，输入两个整数 $a$ 、 $b$ ，（ $0 \leq a < b \leq 100000$ ），表示区间的开始和结束。

输出一个整数，表示能够取得的最多不相交的区间数量。