#P3205. 招聘(200分)
-
1000ms
Tried: 78
Accepted: 26
Difficulty: 6
所属公司 :
华为od
招聘(200分)
题目分析
题目要求计算招聘活动所需的最少面试官数量。每个面试官最多面试 m 人次,且同一时间只能面试一人。面试安排需满足时间不冲突(即后一场面试的开始时间不早于前一场的结束时间)。问题可拆解为两个约束:
- 时间约束:同一面试官的面试场次时间不重叠。
- 场次约束:每个面试官的面试场次不超过 m。
解题思路
-
计算不考虑场次限制时的最少面试官数量(k0):
- 使用贪心算法解决区间分组问题。
- 将面试区间按开始时间排序。
- 维护一个小顶堆,存储每组(面试官)的结束时间。
- 遍历每个区间:
- 若当前区间的开始时间大于等于堆顶的结束时间,则接在该组后面(更新堆顶为当前区间的结束时间)。
- 否则,新建一组(将当前区间的结束时间加入堆中)。
- 堆的大小即为 k0。
-
计算考虑场次限制时的面试官数量:
- 每个面试官最多面试 m 场,因此面试官数量至少为 ⌈n/m⌉。
- 最终答案为 max(⌈n/m⌉,k0)。
复杂度分析
- 时间复杂度:O(nlogn),其中 n 为面试场次。排序耗时 O(nlogn),堆操作每次 O(logk0),总操作 O(nlogk0)。
- 空间复杂度:O(n),存储区间和堆。
代码实现
Python
import heapq
def main():
m = int(input().strip())
n = int(input().strip())
intervals = []
for _ in range(n):
s, e = map(int, input().split())
intervals.append((s, e))
# 按开始时间排序
intervals.sort(key=lambda x: x[0])
# 使用最小堆存储每组的结束时间
heap = []
for s, e in intervals:
if heap and heap[0] <= s:
# 当前区间可接在结束时间最早的组后面
heapq.heappop(heap)
heapq.heappush(heap, e)
k0 = len(heap)
# 计算 ceil(n/m)
min_required_by_m = (n + m - 1) // m
ans = max(min_required_by_m, k0)
print(ans)
if __name__ == "__main__":
main()
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
int[][] intervals = new int[n][2];
for (int i = 0; i < n; i++) {
intervals[i][0] = sc.nextInt();
intervals[i][1] = sc.nextInt();
}
// 按开始时间排序
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
// 使用最小堆存储每组的结束时间
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int[] interval : intervals) {
int s = interval[0], e = interval[1];
if (!heap.isEmpty() && heap.peek() <= s) {
heap.poll(); // 移除堆顶
}
heap.offer(e); // 加入新结束时间
}
int k0 = heap.size();
// 计算 ceil(n/m)
int minRequiredByM = (n + m - 1) / m;
int ans = Math.max(minRequiredByM, k0);
System.out.println(ans);
}
}
C++
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
int m, n;
cin >> m >> n;
vector<pair<int, int>> intervals;
for (int i = 0; i < n; i++) {
int s, e;
cin >> s >> e;
intervals.push_back({s, e});
}
// 按开始时间排序
sort(intervals.begin(), intervals.end());
// 使用最小堆存储每组的结束时间
priority_queue<int, vector<int>, greater<int>> heap;
for (auto& interval : intervals) {
int s = interval.first, e = interval.second;
if (!heap.empty() && heap.top() <= s) {
heap.pop(); // 移除堆顶
}
heap.push(e); // 加入新结束时间
}
int k0 = heap.size();
// 计算 ceil(n/m)
int minRequiredByM = (n + m - 1) / m;
int ans = max(minRequiredByM, k0);
cout << ans << endl;
return 0;
}
题目内容
某公司组织一场公开招聘活动,假设由于人数和场地的限制,每人每次面试的时长不等,并已经安排给定,用 (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 名面试官