503. 区间分组
时间限制：1000 MS 内存限制：64 MB
题目描述
# 区间分组 ## 题目描述 给定 $N$ 个闭区间 $[a_i,b_i]$，请将这些区间分成若干组，使得每个区间恰好属于一个组，且每组内任意两个区间均不相交，并使组数尽可能小。 区间为闭区间，共享端点的两个区间视为相交。 请输出最小组数。 ## 输入格式 从文件 `grouping.in` 中读入数据。 第一行包含一个整数 $N$，表示区间的数量。 接下来 $N$ 行，每行包含两个整数 $a_i,b_i$，表示一个闭区间的左右端点。 ## 输出格式 将结果输出到文件 `grouping.out`。 输出一个整数，表示最小组数。 ## 数据范围 - $1 \le N \le 10^5$。 - $-10^9 \le a_i \le b_i \le 10^9$。 ## 样例输入 ``` 3 -1 1 2 4 3 5 ``` ## 样例输出 ``` 2 ``` ## 样例说明 可以将区间 $[-1,1]$ 和 $[2,4]$ 分为一组，将区间 $[3,5]$ 分为另一组。 由于 $[2,4]$ 与 $[3,5]$ 相交，不能将所有区间放在同一组，因此最小组数为 $2$。 ## 时间与内存限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$64$ MB。