華為面試題： 招聘

題目

某公司組織一場公開招聘活動，假設由於人數和場地的限制，每人每次面試的時長不等，並已經安排給定，用 (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 人次，所以只需要 1 名面試官。

示例3
輸入

3
3
8 35
5 10
1 3

輸出

2

說明：
總共有3 場面試【5，10】和 【8，35】 有重疊，所以至少需要 2 名面試官。

分析

首先進行一下排序，然後用一個大頂堆，維護當前每次面試的結束時間，
然後當一個新的時間安排出現的時候，只需要判斷一下是否需要新的一個面試官，還是繼續使用之前的會議室。

代碼

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    
    int m,n;
    cin >> m >> n;
    vector<pair<int,int>> cap;
    for(int i = 0; i < n; ++i){
    
        int tmp1,tmp2;
        cin >> tmp1 >> tmp2;
        cap.push_back({
    tmp1,tmp2});
    }
    sort(cap.begin(),cap.end(),[](pair<int,int>&a, pair<int,int>&b){
    
        return a.first < b.first;
    });
    vector<priority_queue<int>> cap2(1);
    for(int i = 0; i < cap.size(); ++i){
    
        auto x = cap[i];
        priority_queue<int> tmp;
        int flag = 1;
        for(int i = 0; i < cap2.size(); ++i){
    
            if(cap2[i].empty() || cap2[i].top() <= x.first){
    
                cap2[i].push(x.second);
                flag = 0;
                break;
            }
        }
        if(flag){
    
            tmp.push(x.second);
            cap2.push_back(tmp);
        }
    }
    int ans = 0;
    for(int i = 0;i < cap2.size(); ++i){
    
        int tmp = cap2[i].size();
        ans += tmp % m ? (tmp / m + 1) : ( tmp / m );
    }
    cout << ans << endl;
    return 0;
}