#W1017. 会议排队

会议排队

题目背景

某公司的会议室非常抢手,由于只有一间会议室,多场时间冲突的会议无法同时进行。为了让会议室的利用效率最大化,行政主管需要一份排程方案,以确定在一天内最多能安排多少场会议。

题目描述

给定 nn 场会议的开始时间 SiS_i 和结束时间 EiE_i

在同一时刻,会议室只能容纳一场会议。如果一场会议的结束时间恰好等于另一场会议的开始时间,这两场会议可以连续举行。 请你计算在不发生时间冲突的情况下,最多能参加的会议数量。

输入格式

第一行包含一个整数 nn,表示会议的总数 (1n1051 \leq n \leq 10^5)。

接下来的 nn 行,每行包含两个整数 SiS_iEiE_i,分别表示第 ii 场会议的开始时间和结束时间 (0Si<Ei1090 \leq S_i < E_i \leq 10^9)。

输出格式

一个整数,表示最多能安排的会议场数。

样例

3
10 15
12 20
15 30
2

样例解释

第一场会议在 15 时结束,第三场会议在 15 时开始,两者不冲突,可以连续参加。第二场会议与前后两场均有时间重叠,因此最多只能参加 2 场。