共享汽车(Shared Cars)

题目描述

有 N 个人申请租车，第 i 人申请从第 Sᵢ 天早晨开始使用，到第 Tᵢ 天晚上归还。为了满足所有申请，至少需要多少辆车？

输入格式

• 第一行：单个整数 N；
• 第二行到第 N+1 行：第 i+1 行有两个整数 Sᵢ 与 Tᵢ。

输出格式

单个整数，表示至少需要的车辆数。

数据范围

• 对于 40% 的数据，1 ≤ n ≤ 15；
• 对于 70% 的数据，1 ≤ n ≤ 5000；
• 对于 100% 的数据，1 ≤ n ≤ 100,000；
• 1 ≤ Sᵢ ≤ Tᵢ ≤ 1,000,000。

样例输入 #1

3 1 3 3 5 2 4

样例输出 #1

3

说明：三人各需要一辆车

样例输入 #2

3 1 10 20 30 40 50

样例输出 #2

1

知识点与难度

本题涉及的知识点从属于 GESP 4级，难度等级：⭐⭐。

测试点分布