题目分析

题目要求计算招聘活动所需的最少面试官数量。每个面试官最多面试 $m$ 人次，且同一时间只能面试一人。面试安排需满足时间不冲突（即后一场面试的开始时间不早于前一场的结束时间）。问题可拆解为两个约束：

1. 时间约束：同一面试官的面试场次时间不重叠。
2. 场次约束：每个面试官的面试场次不超过 $m$。

解题思路

1. 计算不考虑场次限制时的最少面试官数量（$k0$）：
   • 使用贪心算法解决区间分组问题。
   • 将面试区间按开始时间排序。
   • 维护一个小顶堆，存储每组（面试官）的结束时间。

题目内容

某公司组织一场公开招聘活动，假设由于人数和场地的限制，每人每次面试的时长不等，并已经安排给定，用 $(S1,E1)$ 、 $(S2,E2)$、 $(Sj,Ej)$…($Si < Ei$，均为非负整数)表示每场面试的开始和结束时间。

面试采用一对一的方式，即一名面试官同时只能面试一名应试者，一名面试官完成一次面试后可以立即进行下一场面试，且每个面试官的面试人次不超过 $m$ 。

为了支撑招聘活动高效顺利进行，请你计算至少需要多少名面试官。

输入描述

输入的第一行为面试官的最多面试人次 $m$，第二行为当天总的面试场次 $n$，

接下来的 $n$ 行为每场面试的起始时间和结束时间，起始时间和结束时间用空格分隔。

其中， $1 <= n, m <= 500$

输出描述

输出一个整数，表示至少需要的面试官数量。

样例1

输入

2
5
1 2
2 3
3 4
4 5
5 6

输出

3

说明

总共有 $5$ 场面试，且面试时间都不重叠，但每个面试官最多只能面试 $2$ 人次，所以需要 $3$ 名面试官。

样例2

输入

3
3
1 2
2 3
3 4

输出

1

说明

总共有 $3$ 场面试，面试时间不重叠，每个面试官最多能面试 $3$ 人次，所以只需要一名面试官

样例3

输入

3
3
8 35
5 10
1 3

输出

2

说明

总共有 $3$ 场面试，$[5,10]$ 和 $[8,35]$ 有重叠，所以至少需要 $2$ 名面试官