I Candy distribution problem

Solution: greedy algorithm

If you want to separate the least candy, use the greedy idea. It must be that if the adjacent position does not increase, everyone will be divided into 1. If the adjacent position increases, it will be good to add 1 to the number of candy. Under what circumstances will candy be added? There is a score difference between adjacent positions, which may be increasing or decreasing. If it is increasing, candy will be increased by 1 in turn. If it is decreasing, candy will be decreased by 1 in turn? This does not conform to the minimum, because the position reduced to the last decreasing position may not be 1, and the minimum must be added from 1. Then we can add 1 backward from the last decreasing position

• An auxiliary array is used to record the candy distributed by children in each position, and all are initialized to 1
• Traverse the array from left to right. If the right element is larger than the adjacent left element, it means that it is increasing. The number of sweets is the previous one plus 1, otherwise it remains unchanged.
• Traverse the array from right to left. If the left element is larger than the adjacent right element, it means that it is a decreasing part in the original array. If the number of sweets allocated to the left in the previous round is smaller, it will be updated to the number of sweets on the right +1, otherwise it will remain unchanged.
• Accumulate and sum the elements in the auxiliary array.

class Solution {
public:
    int candy(vector<int>& arr) {
        //Record the number of sweets in each position, initially 1
        vector<int> nums(arr.size(), 1); 
        //Traverse from left to right
        for(int i = 1; i < arr.size(); i++){ 
            //If the right side is increasing, increase one at a time
            if(arr[i] > arr[i - 1]) 
                nums[i] = nums[i - 1] + 1; 
        }
        //Record the total number of sweets
        int res = nums[arr.size() - 1]; 
        //Traverse from right to left
        for(int i = arr.size() - 2; i >= 0; i--){ 
            //If the left side is larger but the number of sweets is smaller
            if(arr[i] > arr[i + 1] && nums[i] <= nums[i + 1]) 
                nums[i] = nums[i + 1] + 1; 
            //Cumulative sum
            res += nums[i]; 
        }
        return res;
    }
};

Time complexity: O(n), traversing separately twice
Space complexity: O(n), an auxiliary array that records the number of sweets at each position

II Host scheduling (II)

Solution 1: sorting + traversal comparison (recommended)

When do we need the least hosts when we use greed? It must be that all the intervals do not overlap, and the beginning of each interval does not intersect with the end of the previous interval, so we can let the same host take the trouble to host all the time. But the topic is definitely not such an ideal situation, so we need to judge how many hosts we need to add to the cross section.

• Use the auxiliary array to obtain the start time and end time of individual activities, and then sort the start time and end time respectively, so as to judge whether they intersect later.
• Traverse n activities. If the start time of an activity is greater than the end time of the previous activity, the current host is enough, and the end time of the activity is one later.
• If the end time of the previous activity is later than the start time of the current activity, you need to add a host.

class Solution {
public:
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
        vector<int> start;
        vector<int> end;
        //Get the start time of the activity respectively
        for(int i = 0; i < n; i++){
            start.push_back(startEnd[i][0]);
            end.push_back(startEnd[i][1]);
        }
        //Sort start and end times respectively
        sort(start.begin(), start.end());
        sort(end.begin(), end.end());
        int res = 0;
        int j = 0;
        for(int i = 0; i < n; i++){
            //The newly started program is longer than the end time of the previous round, and the host remains unchanged
            if(start[i] >= end[j]) 
                j++;  
            else
                //Moderator increase
                res++;  
        }
        return res;
    }
};

Time complexity: O(n log ⁡ 2 \log_2 log2 n) traversal is O(n), and sort is O(n) log ⁡ 2 \log_2 log2​n)
Space complexity: O(n), an array of auxiliary space records start time and end time

Solution 2: heavy load sorting + large top heap

• Overload the sort function, and put the activities with earlier start time in front. In the same case, consider the activities with earlier end time.
• Use the small top heap assist, where the top of the heap is the end time of the activity that has not yet ended and will end fastest.
• First, add the minimum number of int to the heap and traverse each start time. If the end time at the top of the heap is less than the current start time, you can pop it up, indicating that there is less need for a host.
• In addition, each time, the current end time needs to be added to the heap. Representatives need a host. Finally, the traversal is completed. As many elements are left in the heap, so many hosts are needed.

class Solution {
public:
    //Compare the start time first, and then the end time
    static bool comp(vector<int>& a, vector<int>& b){ 
        if(a[0] == b[0])
            return a[1] < b[1];
        else
            return a[0] < b[0];
    }
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
        sort(startEnd.begin(), startEnd.end(), comp);
        //Small top pile
        priority_queue<int, vector<int>, greater<int> > q; 
        //There may be negative intervals
        q.push(INT_MIN); 
        for(int i = 0; i < n; i++){
            //The latest activity end time is less than the current activity start time
            if(q.top() <= startEnd[i][0])  
               q.pop();
            q.push(startEnd[i][1]);
        }
        //The remaining activities are equal to the number of hosts
        return q.size();
    }
};

Time complexity: O(n log ⁡ 2 \log_2 log2 n), sort is O(n log ⁡ 2 \log_2 log2 n), one traversal, maintaining the heap every time in the loop (n log ⁡ 2 \log_2 log2​n)
Space complexity: O(n), the maximum heap size is n