题解 | #主持人调度（二）#

如何用贪心思想完成最少的主持人调度？

利用贪心思想，如果当前活动的开始和结束时间和其他活动的开始结束时间不重合时，这个主持人就可以继续主持活动，如果两个活动时间有交叉则要增派主持人。但是题目给出的活动时间不一定是按时间顺序排列的，同一时间段可能有多个活动。因此需要自己整理好开始时间和结束时间的排序，如果当前活动的开始时间大于等于之前活动的最小结束时间，说明当前主持人可以继续主持，否则就需要增派主持人。

参考

https://blog.nowcoder.net/n/147d14b917ba4eaca2c951628aaa5a30?f=comment

https://blog.nowcoder.net/n/50fb50f98d6d472bb00d4c1e6ae7ce61?f=comment

export function minmumNumberOfHost(n: number, startEnd: number[][]): number {
    // write code here
    let count = 0;
    let index = 0;  // 当前最小的活动结束时间
    const startActivity: number[] = [];
    const endActivity: number[] = [];

    for (let i = 0; i < n; ++i) {
        startActivity.push(startEnd[i][0]);
        endActivity.push(startEnd[i][1]);
    }

    // 首先要排序，因为数组中多个活动不一定按时间顺序排列
    startActivity.sort((a, b) => a-b);
    endActivity.sort((a, b) => a-b);

    for (let i = 0; i < n; ++i) {
        if (startActivity[i] >= endActivity[index]) {
            ++index;  // 当前主持人可以继续第index个活动，看下一次的活动是否需要增加主持人
        }
        else {
            ++count;
        }
    }

    return count;
}