Huawei interview question: Recruitment

subject

A company organizes an open recruitment campaign , It is assumed that due to the limitation of number of people and site , The length of each interview varies , And has arranged for a given , use (S1, E1)、 (S2, E2)、 (Sj,Ej)…(Si < Ei , All non negative integers ） Indicate the start and end time of each interview . The interview is one-on-one , That is, an interviewer can only interview one candidate at the same time , After an interviewer completes an interview, he can immediately proceed to the next interview , And the number of interviewees of each interviewer shall not exceed m .

In order to support the efficient and smooth progress of recruitment activities , Please calculate how many interviewers you need at least .

Input description
The first line you enter is the maximum number of interviewers m , The second is the total number of interviews on that day n , Next n Behavior
Start time and end time of each interview , Start and end times are separated by spaces . among , 1 <= n, m <= 500

Output description
Output an integer , Indicates the minimum number of interviewers needed .

Example 1

Input

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

Output

3

explain ：
All in all 5 Interview , And the interview time does not overlap , But each interviewer can only interview at most 2 Person time , So we need to 3 An interviewer .

Example 2
Input

3
3
1 2
2 3
3 4

Output

1

explain ：
All in all 3 Interview , Interview times don't overlap , Each interviewer can interview at most 3 Person time , So you just need to 1 An interviewer .

Example 3
Input

3
3
8 35
5 10
1 3

Output

2

explain ：
All in all 3 Interview 【5,10】 and 【8,35】 There is overlap , So at least 2 An interviewer .

analysis

First, sort , Then use a big top pile , Maintain the current end time of each interview ,
Then when a new schedule appears , Just decide whether you need a new interviewer , Or continue to use the previous conference room .

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