ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

6346: 2020完善程序2：最小区间覆盖

内存限制：256 MB 时间限制：2 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：2 通过：2
提交提交记录统计Web Board

题目描述

给出 n 个区间，第 i 个区间的左右端点是 [ai,bi]。现在要在这些区间中选出若干个，使得区间 [0, m] 被所选区间的并覆盖（即每一个 0≤i≤m 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。

输入格式

输入第一行包含两个整数 n 和 m （1≤n≤5000,1≤m≤109） 

接下来 n 行，每行两个整数 ai，bi （0≤ai,bi≤m）

输出格式

所选区间个数的最小值。

输入样例 复制 

3 10
0 8
5 10
0 10

输出样例 复制 

1

分类标签