Niuke.com: host scheduling

  There are two ways to do , Greed and sequencing ：

Catalog

1. greedy

2. Sort

---

1. greedy

It is easy to think of greedy algorithm here , But how to deal with it ？ It's easy to think of sorting , Here we sort the start time and end time . Then we maintain one thing ：

1. The start time of the current activity

2. The last fastest ending time or the last fastest ending time

The second one here is a little difficult to understand , Let's go through the processing ideas ：

Set the start time start[i] And end time end[j], The two sequences here are the results of our sorting of start time and end time

1. If start[i]>=end[j], Explain that the last activity just ended , Explain that we can draw a host directly from the previous activity , Then we don't need another host at all , At this time, we will end the previous activity and look at the next one , namely j++

2. otherwise , Explain the need to increase the number of facilitators

The code is as follows ：

class Solution {
public:
    /**
     *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly 
     *
     *  Calculate how many hosts are needed to successfully host the event 
     * @param n int integer   Yes n An activity 
     * @param startEnd int integer vector<vector<>> startEnd[i][0] Used to indicate the i The start time of the event ,startEnd[i][1] It means the first one i End time of activity 
     * @return int integer 
     */    
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
        vector<int> start;
        vector<int> end;
        for(int i=0;i<n;++i){
            start.push_back(startEnd[i][0]);
            end.push_back(startEnd[i][1]);
        }
        sort(start.begin(), start.end());
        sort(end.begin(), end.end());
        int res=0;
        int j=0;
        for(int i=0;i<n;++i){
            if(start[i]>=end[j]){
                j++;
            }else{
                res++;
            }
        }
        return res;
    }
};

The time complexity here is O(nlogn) 

2. Sort

Sort by heap , In essence, it still uses the previous thought , That is, the current activity borrows from the previous unfinished activity , If you can borrow , Then the number will remain the same , If you can't borrow , Then the number should be increased by one .

The specific operations are as follows ：

First sort the array , according to start Time first end Sort from small to large

Then we maintain a minimum heap , This heap maintenance end time , The meaning of heap top is the earliest end time of an activity ：

1. If the current active time start time is greater than or equal to the heap top , Then explain that you can borrow a host from the front , Direct stack top pop And then again push The end time of the current activity

2. otherwise , direct push

such , The number of nodes left is the minimum number of hosts

Negative numbers may occur in the implementation , So start with pushINT_MIN, To ensure that the first host is added

class Solution {
public:
    /**
     *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly 
     *
     *  Calculate how many hosts are needed to successfully host the event 
     * @param n int integer   Yes n An activity 
     * @param startEnd int integer vector<vector<>> startEnd[i][0] Used to indicate the i The start time of the event ,startEnd[i][1] It means the first one i End time of activity 
     * @return int integer 
     */ 
    bool cmp(vector<int> &a, vector<int> &b){
        if(a[0]==a[0]){
            return a[1]<b[1];
        }
        return a[0]<b[0];
    }
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
        sort(startEnd.begin(), startEnd.end());
        priority_queue<int, vector<int>, greater<int>> q;
        q.push(INT_MIN);
        for(int i=0;i<n;++i){
            if(q.top()<=startEnd[i][0]){
                   q.pop();
            }
            q.push(startEnd[i][1]);
        }
        return q.size();
    }
};