题目分析
题目要求计算招聘活动所需的最少面试官数量。每个面试官最多面试 m 人次,且同一时间只能面试一人。面试安排需满足时间不冲突(即后一场面试的开始时间不早于前一场的结束时间)。问题可拆解为两个约束:
- 时间约束:同一面试官的面试场次时间不重叠。
- 场次约束:每个面试官的面试场次不超过 m。
解题思路
- 计算不考虑场次限制时的最少面试官数量(k0):
- 使用贪心算法解决区间分组问题。
- 将面试区间按开始时间排序。
P3205.招聘(200分)
题目内容
某公司组织一场公开招聘活动,假设由于人数和场地的限制,每人每次面试的时长不等,并已经安排给定,用 (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 名面试官