题解 | #主持人调度(二)#
主持人调度(二)
https://www.nowcoder.com/practice/4edf6e6d01554870a12f218c94e8a299
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 计算成功举办活动需要多少名主持人 * @param n int整型 有n个活动 * @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间,startEnd[i][1]表示第i个活动的结束时间 * @return int整型 */ function minmumNumberOfHost(n, startEnd) { let res = 0, s = [], e = [], endIndex = 0; startEnd.forEach((i) => { s.push(i[0]); e.push(i[1]); }); s = s.sort((a, b) => a - b); e = e.sort((a, b) => a - b); for (let i = 0; i < n; i++) { if (s[i] >= e[endIndex]) { endIndex++; } else { res++; } } return res; } module.exports = { minmumNumberOfHost };
题目要求:
n 场表演,肯定都是按照开始时间排好序一场一场的演出。由于一个主持人同一时间段只能主持一场演出,那么演完n场表演最少需要几个主持人。
分析:
一场表演开始需不需要加主持人,关键看前面的演出有没有结束。如果前面的演出结束了,这一场就不需要加主持人;如果前面的演出还没结束那就需要加人。
到最后一场演出开始的时候,排上的主持人就是n场表演需要安排最少的主持人人数。
endIndex 就是标记最近一场表演结束的场次,根据endIndex可以得到最近一场的结束时间。
最少主持人数,也是n场表演时间最多重叠的部分。