Question d'entrevue de Huawei: recrutement

Titre

Une entreprise organise une campagne de recrutement ouverte,Supposons qu'en raison de la limitation du nombre de personnes et du site,La durée de chaque entrevue varie d'une personne à l'autre,Et a été programmé pour,Avec (S1, E1)、 (S2, E2)、 (Sj,Ej)…(Si < Ei ,Sont des entiers non négatifs ）Indique les heures de début et de fin de chaque entrevue.L'entrevue est individuelle,C'est - à - dire qu'un intervieweur ne peut interviewer qu'un seul candidat en même temps,Un intervieweur peut passer à l'entrevue suivante immédiatement après avoir terminé une entrevue,Et chaque intervieweur n'a pas plus de m .

Afin de soutenir le bon déroulement des activités de recrutement,Veuillez calculer le nombre minimum d'intervieweurs requis.

Description des entrées
Première ligne entrée Nombre maximum de personnes interviewées par l'intervieweur m ,Nombre total de séances d'entrevue le jour du deuxième acte n ,La suite. n Comportement
Heure de début et de fin de chaque entrevue,Les heures de début et de fin sont séparées par des espaces. Parmi eux, 1 <= n, m <= 500

Description des produits
Sortie d'un entier,Indique le nombre minimum d'intervieweurs requis.

Exemple1

Entrée

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

Produits

3

Description ：
En tout.5 Un entretien.,Et les entrevues ne se chevauchent pas,Mais chaque intervieweur ne peut interviewer que 2 Nombre de personnes,Il faut donc 3 Intervieweur.

Exemple2
Entrée

3
3
1 2
2 3
3 4

Produits

1

Description：
En tout.3 Un entretien.,Les entrevues ne se chevauchent pas, Chaque intervieweur peut interviewer au plus 3 Nombre de personnes,Donc tout ce qu'il faut c'est 1 Intervieweur.

Exemple3
Entrée

3
3
8 35
5 10
1 3

Produits

2

Description：
En tout.3 Un entretien.【5,10】Et 【8,35】 Il y a chevauchement,Donc au moins 2 Intervieweur.

Analyse

Commencez par trier , Et avec une grosse pile , Maintenir l'heure actuelle de fin de chaque entrevue ,
Et quand un nouvel horaire arrive , Il suffit de déterminer si un nouvel intervieweur est nécessaire , Ou continuer à utiliser la salle de réunion précédente .

Code

#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;
}