NC147：主持人调度

- 1、题目描述：

图片说明
- 2、题目链接：

https://www.nowcoder.com/practice/445c44d982d04483b04a54f298796288?tpId=117&tqId=37781&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey
-3、设计思想：
图片说明

-4、视频讲解链接B站视频讲解

-5、代码：
c++版本:

 class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算成功举办活动需要多少名主持人
     * @param n int整型 有n个活动
     * @param startEnd int整型vector<vector<>> startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
     * @return int整型
     */
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
        // write code here
        ///按照起始时间从小到大排序
        sort(startEnd.begin(),startEnd.end(),
             [](vector<int>& a,vector<int>& b){return a[0]==b[0]?a[1]<b[1]:a[0]<b[0];});
        priority_queue<int, vector<int>, greater<int> >pq;///用来控制调度的结束时间
        pq.push(startEnd[0][1]);
        for(int i = 1;i < n;i ++){
            ///如果当前活动的开始时间比前一个任务的结束时间长，那么不需要添加新的主持人
            if(startEnd[i][0] >= pq.top()) pq.pop();
            ///添加新活动的结束时间
            pq.push(startEnd[i][1]);
        }
        return pq.size();
    }
};

Java版本：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算成功举办活动需要多少名主持人
     * @param n int整型 有n个活动
     * @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
     * @return int整型
     */
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        // write code here
        ///按照起始时间从小到大排序
        Arrays.sort(startEnd , (o1 ,o2) -> {
            return o1[0] ==  o2[0] ? o1[1] - o2[1] : o1[0] - o2[0];
        });
         // 保存每一个时间段的终止时间，从小到大
        PriorityQueue<Integer> pq = new PriorityQueue<>();///用来控制调度的结束时间
        pq.offer(startEnd[0][1]);
        for(int i = 1 ; i < n ; i++){
            ///如果当前活动的开始时间比前一个任务的结束时间长，那么不需要添加新的主持人
            if(startEnd[i][0] >= pq.peek()) pq.poll();
            ///添加新活动的结束时间
            pq.offer(startEnd[i][1]);
        }
        return pq.size();
    }
}

Python版本:

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 计算成功举办活动需要多少名主持人
# @param n int整型 有n个活动
# @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
# @return int整型
#
import heapq
class Solution:
    def minmumNumberOfHost(self , n , startEnd ):
        # write code here
        #按照起始时间从小到大排序
        startEnd=sorted(startEnd, key=lambda x:x[0])
        pq = []#用来控制调度的结束时间
        heapq.heappush(pq,startEnd[0][1])
        for i in range(1,n):
            #如果当前活动的开始时间比前一个任务的结束时间长，那么不需要添加新的主持人
            if startEnd[i][0] >= pq[0]:
                heapq.heappop(pq)
            #添加新活动的结束时间
            heapq.heappush(pq, startEnd[i][1])

        return len(pq)

JavaScript版本:

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 计算成功举办活动需要多少名主持人
 * @param n int整型 有n个活动
 * @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
 * @return int整型
 */
function minmumNumberOfHost( n ,  startEnd ) {
     function PriorityQueue() {
        this.heap = []
    }
    PriorityQueue.prototype.up = function(i) {
        const father = Math.floor((i+1)/2) - 1
        if (father < 0) return
        if (this.heap[i] < this.heap[father]) {
            [this.heap[i], this.heap[father]] = [this.heap[father], this.heap[i]]
            this.up(father)
        }
    }
    PriorityQueue.prototype.down = function(i) {
        const l = i*2 + 1
        const r = i*2 + 2
        const n = this.heap.length
        let small = i
        if (l < n && this.heap[l] < this.heap[small]) {
            small  = l
        }
        if (r < n && this.heap[r] < this.heap[small]) {
            small  = r
        }
        if (small != i) {
            [this.heap[i], this.heap[small]] = [this.heap[small], this.heap[i]]
            this.down(small)
        }
    }
    PriorityQueue.prototype.offer = function(val) {
        this.heap.push(val)
        this.up(this.heap.length-1)
    }
    PriorityQueue.prototype.poll = function() {
        this.heap[0] = this.heap[this.heap.length-1]
        this.heap.pop()
        this.down(0)
    }
    PriorityQueue.prototype.peek = function() {
        return this.heap[0]
    }
    PriorityQueue.prototype.size = function() {
        return this.heap.length
    }
    // write code here
    ///按照起始时间从小到大排序

        startEnd.sort((a, b) => (a[0] === b[0])?b[1] - a[1]:a[0] - b[0])
         // 保存每一个时间段的终止时间，从小到大
        const pq = new PriorityQueue();///用来控制调度的结束时间
        pq.offer(startEnd[0][1]);
        for(let i = 1 ; i < n ; i++){
            ///如果当前活动的开始时间比前一个任务的结束时间长，那么不需要添加新的主持人
            if(startEnd[i][0] >= pq.peek()) pq.poll();
            ///添加新活动的结束时间
            pq.offer(startEnd[i][1]);
        }
        return pq.size();
}
module.exports = {
    minmumNumberOfHost : minmumNumberOfHost
};

NC147： 主持人调度

NC147：主持人调度