一、分糖果问题

解法:贪心算法

要想分出最少的糖果，利用贪心思想，肯定是相邻位置没有增加的情况下，大家都分到1，相邻位置有增加的情况下，分到糖果数加1就好。什么情况下会增加糖果，相邻位置有得分差异，可能是递增可能是递减，如果是递增的话，糖果依次加1，如果是递减糖果依次减1？这不符合最小，因为减到最后一个递减的位置可能不是1，必须从1开始加才是最小，那我们可以从最后一个递减的位置往前反向加1

• 使用一个辅助数组记录每个位置的孩子分到的糖果，全部初始化为1.
• 从左到右遍历数组，如果右边元素比相邻左边元素大，意味着在递增，糖果数就是前一个加1，否则保持1不变。
• 从右到左遍历数组，如果左边元素比相邻右边元素大， 意味着在原数组中是递减部分，如果左边在上一轮中分到的糖果数更小，则更新为右边的糖果数+1，否则保持不变。
• 将辅助数组中的元素累加求和。

class Solution {
public:
    int candy(vector<int>& arr) {
        //记录每个位置的糖果数，初始为1
        vector<int> nums(arr.size(), 1); 
        //从左到右遍历
        for(int i = 1; i < arr.size(); i++){ 
            //如果右边在递增，每次增加一个
            if(arr[i] > arr[i - 1]) 
                nums[i] = nums[i - 1] + 1; 
        }
        //记录总糖果数
        int res = nums[arr.size() - 1]; 
        //从右到左遍历
        for(int i = arr.size() - 2; i >= 0; i--){ 
            //如果左边更大但是糖果数更小
            if(arr[i] > arr[i + 1] && nums[i] <= nums[i + 1]) 
                nums[i] = nums[i + 1] + 1; 
            //累加和
            res += nums[i]; 
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

时间复杂度：O(n)，单独遍历两次
空间复杂度：O(n)，记录每个位置糖果数的辅助数组

二、主持人调度（二）

解法一:排序+遍历比较(推荐)

我们利用贪心思想，什么时候需要的主持人最少？那肯定是所有的区间没有重叠，每个区间首和上一个的区间尾都没有相交的情况，我们就可以让同一位主持人不辞辛劳，一直主持了。但是题目肯定不是这种理想的情况，那我们需要对交叉部分，判断需要增加多少位主持人。

• 利用辅助数组获取单独各个活动开始的时间和结束时间，然后分别开始时间和结束时间进行排序，方便后面判断是否相交。
• 遍历n个活动，如果某个活动开始的时间大于之前活动结束的时候，当前主持人就够了，活动结束时间往后一个。
• 若是出现之前活动结束时间晚于当前活动开始时间的，则需要增加主持人。

class Solution {
public:
    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;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

时间复杂度：O(n${\log }_2$n)遍历都是O(n)，sort排序为O(n${\log }_2$n)
空间复杂度：O(n)，辅助空间记录开始时间和结束时间的数组

解法二:重载排序+大顶堆

• 重载sort函数，将开始时间早的活动放在前面，相同情况下再考虑结束时间较早的。
• 使用小顶堆辅助，其中堆顶是还未结束的将要最快结束的活动的结束时间。
• 首先将int的最小数加入堆中，遍历每一个开始时间，若是堆顶的结束时间小于当前开始时间，可以将其弹出，说明少需要一个主持人。
• 除此之外，每次都需要将当前的结束时间需要加入堆中，代表需要一个主持人，最后遍历完成，堆中还有多少元素，就需要多少主持人。

class Solution {
public:
    //优先比较开始时间，再比较结束时间
    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);
        //小顶堆
        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();
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

时间复杂度：O(n${\log }_2$n)，sort排序是O(n${\log }_2$n)，一次遍历，循环中维护堆每次O(n${\log }_2$n)
空间复杂度：O(n)，堆大小最大为n