首页 > 试题广场 >

主持人调度（二）

[编程题]主持人调度（二）
  • 热度指数：83611 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
有 n 个活动即将举办，每个活动都有开始时间与活动的结束时间，第 i 个活动的开始时间是 starti ,第 i 个活动的结束时间是 endi ,举办某个活动就需要为该活动准备一个活动主持人。

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

数据范围: ， -2^{32} \le start_i\le end_i \le 2^{31}-1

复杂度要求：时间复杂度 ，空间复杂度
示例1

输入

2,[[1,2],[2,3]]

输出

1

说明

只需要一个主持人就能成功举办这两个活动
示例2

输入

2,[[1,3],[2,4]]

输出

2

说明

需要两个主持人才能成功举办这两个活动

备注:
start_i,end_i在int范围内
算法知识视频讲解
添加回答
Java
唐氏综合征头像 唐氏综合征
如下是有问题的解法：未考虑多个重叠的区域，可能导致结果偏大，但可以通过 

 public int minmumNumberOfHost(int n, int[][] startEnd) {
        // write code here
        if (startEnd.length <= 1)
            return startEnd.length;
        int len = startEnd.length;

        int[] startArr = new int[len];
        int[] endArr = new int[len];

        for (int i = 0; i < len; i++) {
            startArr[i] = startEnd[i][0];
            endArr[i] = startEnd[i][1];
        }
        Arrays.sort(startArr);
        Arrays.sort(endArr);
        int least = 1;
        int endIndex = 0;
        for (int startIndex = 1; startIndex < len; startIndex++) {
            // 断言没问题，勿质疑
            assert startArr[startIndex] <= endArr[startIndex];
            if(startArr[startIndex] >= endArr[endIndex])
                endIndex ++;
            else
                least ++;
        }

        return least;
    }
如下是正确的做法，当 startIndex < endIndex 时需要一个主持人，继续增加 startIndex, 如果仍然满足，则说明时间区间重叠，继续增加主持人，如果不满足，则说明上一个活动已经结束，可以释放一名主持人，求出这个过程中的最大的主持人数即可， while 循环保证了可以一一删除多个已经干完活儿的主持人，即使是多个end时间重叠的也是合理的 
 public int minmumNumberOfHost(int n, int[][] startEnd) {
    if (n <= 1) return n;

    int[] startArr = new int[n];
    int[] endArr = new int[n];

    for (int i = 0; i < n; i++) {
        startArr[i] = startEnd[i][0];
        endArr[i] = startEnd[i][1];
    }
    Arrays.sort(startArr);
    Arrays.sort(endArr);

    int maxHosts = 0;
    int currentHosts = 0;
    int startIndex = 0;
    int endIndex = 0;

    while (startIndex < n && endIndex < n) {
        if (startArr[startIndex] < endArr[endIndex]) {
            currentHosts++;
            startIndex++;
        } else {
            currentHosts--;
            endIndex++;
        }
        maxHosts = Math.max(maxHosts, currentHosts);
    }

    return maxHosts;
}
发表于 2024-07-04 09:03:13 回复(0)
Java
做则必成的勇气和信心头像 做则必成的勇气和信心 
public int minmumNumberOfHost (int n, int[][] startEnd) {
        //贪心
        int[] start=new int[n];
        int[] end=new int[n];
        //分别获得开始/结束的时间
        for(int i=0;i<n;i++){
            start[i]=startEnd[i][0];
            end[i]=startEnd[i][1];
        }
        //对开始/结束时间排序
        Arrays.sort(start);
        Arrays.sort(end);
        int ans=1;//主持人数初始化为1
        int j=0;
        for(int i=1;i<n;i++){//i从1开始，而不是从0开始
            if(start[i]>=end[j]){//新开始的时间>=上一个结束的时间
                j++;
            }else{
                ans++;//如果重叠了，那就主持人+1
            }
        }
        return ans;
    }

发表于 2023-07-21 16:48:40 回复(0)
Java
loser666头像 loser666
图片来自HHHChen77，在此致谢！！！
startTime和endTime分别排序后，使用双指针，类似合并有序链表/数组的思想
如果有活动开始，count++；有活动结束，count--；既有活动开始又有活动结束，count不动 
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, ArrayList<ArrayList<Integer>> startEnd) {
        // write code here
        int[] startTime = new int[n];
        int[] endTime = new int[n];
        for (int i = 0; i < n; i++) {
            startTime[i] = startEnd.get(i).get(0);
            endTime[i] = startEnd.get(i).get(1);
        }
        Arrays.sort(startTime);
        Arrays.sort(endTime);

        int res = 0;
        int i = 0, j = 0, count = 0;
        while (i < n && j < n) {
            if (startTime[i] < endTime[j]) {
                count++;
                i++;
            } else if (startTime[i] > endTime[j]) {
                count--;
                j++;
            } else {
                // startTime[i] == endTime[j]
                i++;
                j++;
            }
            res = Math.max(res, count);
        }
        return res;
    }
}



发表于 2022-09-19 23:31:21 回复(1)
Java
cooking969头像 cooking969 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算成功举办活动需要多少名主持人
     * @param n int整型 有n个活动
     * @param startEnd int整型ArrayList<ArrayList<>> startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
     * @return int整型
     */
    public int minmumNumberOfHost (int n, ArrayList<ArrayList<Integer>> startEnd) {
        // write code here
        int[] start = new int[n];
        int[] end = new int[n];
        for(int i = 0; i < startEnd.size(); i++) {
            start[i] = startEnd.get(i).get(0);
            end[i] = startEnd.get(i).get(1);
        }
        Arrays.sort(start, 0, start.length);
        Arrays.sort(end, 0, end.length);
        int res = 0;
        int j = 0;
        for(int i = 0; i < n; i++){
            if(start[i] >= end[j])
                j++; 
            else
                res++; 
        }
        return res;
    }
}

发表于 2022-09-13 04:59:38 回复(0)
Java
yxjing头像 yxjing 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算成功举办活动需要多少名主持人
     * @param n int整型 有n个活动
     * @param startEnd int整型ArrayList<ArrayList<>> startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
     * @return int整型
     */
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        // write code here
        //ArrayList<ArrayList<Integer>>
        int[] start=new int[n];
        int[] end=new int[n];
        for(int i=0;i<=n-1;i++){
//             start[i]=startEnd.get(i).get(0);
//             end[i]=startEnd.get(i).get(1);
            start[i]=startEnd[i][0];
            end[i]=startEnd[i][1];
        }
        Arrays.sort(start);
        Arrays.sort(end);
        
        int host=1;
        int j=0;
        
        for(int i=1;i<=n-1;++i){
            if(start[i]>=end[j]){
                j++;
            }else{
                host++;
            }
        }
        return host;
        
                                
    }
}

发表于 2022-08-25 15:01:28 回复(0)
Java
牛客用户007头像 牛客用户007
若后一个开始时间晚于前一个结束时间，则最早结束时间向后进1（）否则 需要人数+1； 
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
        int[] start = new int[startEnd.length];
        int[] end = new int[startEnd.length];

        for (int i = 0; i < startEnd.length; i ++) {
            start[i] = startEnd[i][0];
            end[i] = startEnd[i][1];
        }

        Arrays.sort(start);
        Arrays.sort(end);

        int res = 0;
        int index = 0;
        for (int i = 0; i < startEnd.length; i ++) {
            if (start[i] < end[index]) {
                res ++;
            } else {
                index++;
            }
        }

        return res;
    }
}

发表于 2022-08-12 20:52:16 回复(0)
Java
我难顶了头像 我难顶了
Comparator会溢出，我佛了
发表于 2022-03-25 18:21:32 回复(2)
Java
***头像 *** 
   public int minmumNumberOfHost (int n, int[][] startEnd) {
       int start[]=new int[n];
        int end[]=new int[n];
        for(int i=0;i<n;i++){
            start[i]=startEnd[i][0];
            end[i]=startEnd[i][1];
            
        }
        Arrays.sort(start);
        Arrays.sort(end);
        
        int mount=0;
        int ends=0;
        for(int i=0;i<n;i++){
            if(start[i]>=end[ends]){
                ends++;
            }else{
                
                mount++;
            }
            
        }
        return mount;
        
    }

发表于 2022-03-18 16:44:34 回复(0)
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) {
        Arrays.sort(startEnd, (a, b) -> a[0] <= b[0] ? -1 : 1);
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
        int ans = 0;
        for (int[] interval : startEnd) {
            while (!minHeap.isEmpty() && interval[0] >= minHeap.peek()) {
                minHeap.poll();
            }
            minHeap.add(interval[1]);
            ans = Math.max(ans, minHeap.size());
        }
        return ans;
    }
}

发表于 2022-02-28 12:05:03 回复(0)
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) {
        Arrays.sort(startEnd, new Comparator<int[]>() {
            @Override
            public int compare(int[] arr1, int[] arr2) {
                if(arr1[0]>arr2[0]) return 1;
                else if(arr1[0]<arr2[0]){
                    return -1;
                }
                else {
                    return arr1[1]>arr2[1]?1:-1;
                }
            }

        });

        int res=0;
        PriorityQueue<Integer> deque=new PriorityQueue<>();
        for(int i=0;i<n;i++){
            int[]v=startEnd[i];
            while (!deque.isEmpty()&&v[0]>=deque.peek()) deque.poll();

            deque.offer(v[1]);//放入结束时间

            res=Math.max(res,deque.size());
        }
        return res;
    }
}
发表于 2021-12-26 13:24:54 回复(0)
Java
pein531头像 pein531
首先将每个主持任务按开始时间和结束时间升序进行二次排序，然后遍历任务数组。这样就是按时间线来进行遍历，且对于开始时间相同的主持任务，优先选择时间短的，这样才更可能“连轴转”，紧接着做下一个主持任务。接下来可以用小根堆模拟排队过程。
建立一个小根堆存储主持任务的结束时间，意味着可以在O(1)的时间复杂度内知道哪个主持任务能够最早结束，遍历到某个任务时：(1) 如果小根堆的堆顶小于等于当前任务的开始时间，说明做堆顶任务的主持人此时是空闲的，可以把当前主持任务揽下来，因此不需要增加主持人，把堆顶任务弹出，当前任务入堆；(2) 如果小根堆的堆顶大于当前任务的开始时间，这就说明这个最早能“收工”的主持人都没空接下当前任务，堆顶下面任务的主持人当然就更没空了，所以此时不出堆，新任务的结束时间直接入堆，表示需要增加一个主持人。
按时间线遍历下来之后，堆中有几个任务积压，就说明至少需要多少个主持人。 
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, new Comparator<int[]>(){
            @Override
            public int compare(int[] task1, int[] task2){
                if(task1[0] != task2[0]){
                    return task1[0] < task2[0]? -1: 1;
                }else{
                    return task1[1] < task2[1]? -1: 1;
                }
            }
        });
        PriorityQueue<Integer> pq = new PriorityQueue<>();     // 用于存储刚结束活动的end时间
        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();     // 队列中积压的元素数量就是需要的主持人数
    }
}

发表于 2021-12-12 10:25:59 回复(3)
提交观点

问题信息

贪心
难度：
12条回答 7829浏览

热门推荐

通过挑战的用户

查看代码

相关试题

主持人调度（二）

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号