48. 安排讲座(第六期模拟笔试)

内存限制:128 MB 时间限制:1.000 S

题目描述

小明是一位的科学家,不久前他参加了一场重要的国际科学大会,展示了他的最新研究成果。现在,他计划在一所高校举办讲座,以分享他的研究成果。

然而,不同的大学班级有不同的课程安排,因此小明需要根据当天的大学生日程表来决定最佳的讲座时间。在这份日程表上,记录着各个班级的课余时间段,这些时间段都是整数。请问小明应该如何安排他的讲座,以便让尽可能多的班级参加?

输入

第一行为一个整数 N,代表有 N 个班级 后续有 N 行,每行两个整数,代表了不同班级的课余时间段

输出

输出一个正整数,代表最多能安排多少场讲座。

样例输入 复制

5
4 5
6 7
6 8
7 10
9 11

样例输出 复制

3

提示

因为不同班级的课余时间不同,而小明每个时间段只能安排一场讲座。

每场讲座只有一个班级能够参加。

小明只能选择课余时间段为 [[4, 5], [6, 7], [7, 10]] 或  [[4, 5], [6, 7], [9, 11]] 等没有时间冲突的班级(课余时间段连续的情况不算冲突),所以在输入用例中,小明最多只能安排三场讲座。

数据范围:
1 <= N < 100。
1 <= 课余时间数字范围 <= 24。