浇水问题

题目描述

中间的直线表示需要浇水的植被，范围最左端是 $0$，最右端是 $m$。现有 $n$ 个自动灌溉设备，每个灌溉设备自动洒水的范围不确定。问，最少开通多少个设备，可以灌溉所有植被。如果有不能灌溉的情况，输出 $-1$。

输入格式

第一行两个整数，分别是 $m$ 和 $n$。接着输入 $n$ 行，每行 $2$ 个整数，分别是每个灌溉设备覆盖的左端点和右端点。

输出格式

最少开通灌溉设备的个数。如果有不能灌溉的情况，输出 $-1$。

样例输入 #1

5
3
-1 3
2 4
3 5

样例输出 #1

2

数据范围

$0 < m \le 10000$，$0 < n \le 10000$。

知识点与难度

本题涉及的知识点从属于 GESP五级（贪心算法、区间覆盖），难度等级：⭐⭐⭐⭐。

测试点分布