鸟巢场馆安排

解题思路

• 本题可抽象为：给定 $n$ 个闭区间 $[s_i,e_i]$，选出尽可能多的区间，使得它们两两不重叠（端点重合也算重叠，与题面「包括起始时间与结束时间」一致）。
• 经典模型是区间调度 / 活动选择：将所有区间按结束时间 $e_i$ 升序排序（$e_i$ 相同时按 $s_i$ 升序打破并列），然后从左到右贪心：若当前区间起点 $s_i$ 严格大于上一个已选区间的终点 $last$，则选取该区间，并令 $last \leftarrow e_i$。
• 直观理解：在「不重叠」前提下，越早结束的活动越不挡后面的区间，因此每次在「与已安排不冲突」的候选里选结束最早的一定最优；可用交换论证严格证明。
• 实现上读入 $n$，再读一行共 $2n$ 个整数，按顺序两两组成区间即可。

题目内容

$2008$ 年奥运会举行完成后，鸟巢场馆面临空置的问题。政府希望对外开放鸟巢，允许各公司申请使用。各公司需要提前提交申请，说明使用鸟巢场馆的起始时间与截止时间。公司申请的时间端（包括起始时间与结束时间）独自占用鸟巢，不可以安排其它公司。鸟巢管理方需要合理安排，保证尽可能多的公司都使用到。

在申请截止时间内，收到许多公司的报名。请你设计一个方案，保证尽可能多的公司能够使用到鸟巢。

输入描述

申请公司数

各公司申请的初始时间与结束时间

输出描述

最大可安排公司数量

样例1

输入

4
4 9 9 11 13 19 10 17

输出

2

说明

用例各公司起始与结束时间均合法，请不要校验。