题目描述

有n个点和m个区间，点和区间的端点全部是整数，对于点a和区间[b,c]，若a>=b且a<=c，称点a满足区间[b,c]。　　求最小的点的子集，使得所有区间都被满足。 输入格式 　　第一行两个整数n m　　以下n行 每行一个整数，代表点的坐标　　以下m行 每行两个整数，代表区间的范围 输出格式 　　输出一行，最少的满足所有区间的点数，如无解输出-1。 样例输入 5 5263872 53 43 32 76 9 样例输出 2 数据规模和约定 　　1<=n,m<=10000　　0<=点和区间的坐标<=50000

输入格式

第一行两个整数n m　　以下n行 每行一个整数，代表点的坐标　　以下m行 每行两个整数，代表区间的范围 输出格式 　　输出一行，最少的满足所有区间的点数，如无解输出-1。 样例输入 5 5263872 53 43 32 76 9 样例输出 2 数据规模和约定 　　1<=n,m<=10000　　0<=点和区间的坐标<=50000

输出格式

输出一行，最少的满足所有区间的点数，如无解输出-1。 样例输入 5 5263872 53 43 32 76 9 样例输出 2 数据规模和约定 　　1<=n,m<=10000　　0<=点和区间的坐标<=50000

5 5263872 53 43 32 76 9
样例输出
2
数据规模和约定
　　1<=n,m<=10000　　0<=点和区间的坐标<=50000

2
数据规模和约定
　　1<=n,m<=10000　　0<=点和区间的坐标<=50000

来源

蓝桥杯 算法提高