解题思路

本题是经典的 区间调度问题，目标是在若干时间区间中选择最多数量的互不重叠区间。

由于题目允许两个试玩时间连续，例如 [2,3] 和 [3,4] 可以同时安排，所以判断是否冲突时使用：

当前试玩开始时间 >= 上一个已安排试玩结束时间

题目内容

新研发了一台游戏设备可以面向用户接受试玩。现有 $n$ 个试玩申请，每个试玩有开始时间和结束时间。作为协调员，为了能让更多人体验到游戏，你需要对试玩申请进行选择，使得：

1. 任意两个被选中的试玩时间不重叠。

2. 任意两个被选中的试玩时间允许连续，例如 $[2,3]$ 和 $[3,4]$ 认为是可以都被安排的。

3. 被安排的试玩数量最大化。

请问最多能安排多少场试玩？

输入描述

• 第一行：一个整数 $n (1 ≤ n ≤ 10^5)$，表示试玩申请数量。
• 第二行：是一个长度为 $n$ 的数组，数组的每个元素为两个整数 $start$ 和 $end ( 0 ≤ start < end ≤ 10^9$)，表示试玩的开始和结束时间。

输出描述

一个整数，表示最多能安排的试玩数量。

样例1

输入

3,[[1,5],[2,3],[4,6]]

输出

2

说明

选择玩家 $[2,3]$, $[4,6]$, 共 $2$ 位；

如果选择$[1,5]$则跟其他的时间冲突，则只有 $1$ 位，不满足最多玩家的要求。

样例2

输入

5,[[1,2],[3,4],[5,6],[7,8],[9,10]]

输出

5

说明

共有 $5$ 个试玩申请，且时间都不重合，允许连续，因此最多可以安排 $5$ 个试玩。

样例3

输入

1,[[1,5]]

输出

1

说明

只有一个试玩申请，直接安排。

样例4

输入

3,[[1,5],[2,4],[3,6]]

输出

1

说明

所有试玩时间都冲突，只能安排一场。