1. 主持人调度

牛客BM96
有 n 个活动即将举办，每个活动都有开始时间与活动的结束时间，第 i 个活动的开始时间是 starti ,第 i 个活动的结束时间是 endi ,举办某个活动就需要为该活动准备一个活动主持人。

一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，一个主持人参与了第 i 个活动，那么该主持人在 (starti,endi) 这个时间段不能参与其他任何活动。求为了成功举办这 n 个活动，最少需要多少名主持人。

复杂度要求：时间复杂度 O(nlogn) ，空间复杂度 O(n)

输入：
2,[[1,2],[2,3]]
返回值：
1

输入：
2,[[1,3],[2,4]]

返回值：
2
1
2
3
4
5
6
7
8
9
10

注意点：获取二维数组中的的一维，排序从低到高

function minmumNumberOfHost( n ,  startEnd ) {
    // write code hstartEnd.map(item =>item[0])ere
    let start =startEnd.map(item =>item[0]).sort((a,b)=>a-b);
    let end= startEnd.map(item=>item[1]).sort((a,b)=>a-b);
    let count =0,j=0;
    for(let i=0;i<start.length;i++){
       if(start[i]<end[j])
           //某个活动i的开始时间早于活动j 的结束时间，增加主持人
           count++;
        else
            //否则，不用增加主持人
            j++; 
    }
    return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2 分糖果问题

一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：

1. 每个孩子不管得分多少，起码分到一个糖果。
2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)

给定一个数组 arr 代表得分数组，请返回最少需要多少糖果。

要求: 时间复杂度为 O(n) 空间复杂度为 O(n)

输入：
[1,1,2]

返回值：
4

说明：
最优分配方案为1,1,2 
1
2
3
4
5
6
7
8

function candy( arr ) {
    let res=new Array(arr.length).fill(1);
    for(let i=0;i<arr.length;i++)
        if (arr[i+1] > arr[i]){
          res[i+1] = res[i] + 1
        }
    for(let j=arr.length-1;j>0;j--)
        if(arr[j-1]>arr[j] && res[j-1]<=res[j])
            res[j-1]= res[j]+1;
    return res.reduce((pre,cur)=>pre+cur);
}
1
2
3
4
5
6
7
8
9
10
11