504. 区间覆盖
时间限制：1000 MS 内存限制：64 MB
题目描述
# 区间覆盖 ## 题目描述 给定 $N$ 个闭区间 $[a_i,b_i]$ 和一个目标线段 $[s,t]$，请从这 $N$ 个区间中选择尽量少的区间，使它们的并集完全包含目标线段。 覆盖对象为连续线段，而不仅是线段上的整数点。由于区间为闭区间，两个区间可以在端点处相接。 输出所需的最少区间数。如果无法完全覆盖目标线段，则输出 $-1$。 当 $s=t$ 时，目标线段退化为一个点。如果存在给定区间包含该点，则答案为 $1$；否则答案为 $-1$。 ## 输入格式 从文件 `covering.in` 读入数据。 第一行包含两个整数 $s,t$，表示目标线段的两个端点。 第二行包含一个整数 $N$，表示给定区间的数量。 接下来 $N$ 行，每行包含两个整数 $a_i,b_i$，表示一个闭区间的两个端点。 ## 输出格式 输出到文件 `covering.out`。 输出一个整数，表示完全覆盖目标线段所需的最少区间数。如果无法完全覆盖，则输出 $-1$。 ## 数据范围 - $1 \le N \le 10^5$。 - $-10^9 \le a_i \le b_i \le 10^9$。 - $-10^9 \le s \le t \le 10^9$。 ## 样例输入 ``` 1 5 3 -1 3 2 4 3 5 ``` ## 样例输出 ``` 2 ``` ## 样例说明 选择区间 $[-1,3]$ 和 $[3,5]$，即可完全覆盖目标线段 $[1,5]$。没有单个给定区间能够覆盖目标线段，因此最少需要选择 $2$ 个区间。 ## 资源限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$64$ MB。