题目分析

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

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

解题思路

1. 计算不考虑场次限制时的最少面试官数量（$k0$）：

   • 使用贪心算法解决区间分组问题。
   • 将面试区间按开始时间排序。
   • 维护一个小顶堆，存储每组（面试官）的结束时间。
   • 遍历每个区间：
     • 若当前区间的开始时间大于等于堆顶的结束时间，则接在该组后面（更新堆顶为当前区间的结束时间）。
     • 否则，新建一组（将当前区间的结束时间加入堆中）。
   • 堆的大小即为 $k0$。

2. 计算考虑场次限制时的面试官数量：

   • 每个面试官最多面试 $m$ 场，因此面试官数量至少为 $\lceil n / m \rceil$。
   • 最终答案为 $\max(\lceil n / m \rceil, k0)$。

复杂度分析

• 时间复杂度：$O(n \log n)$，其中 $n$ 为面试场次。排序耗时 $O(n \log n)$，堆操作每次 $O(\log k0)$，总操作 $O(n \log k0)$。
• 空间复杂度：$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$ 名面试官