首页 > 试题广场 >

主持人调度（二）

[编程题]主持人调度（二）

热度指数：85358 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

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

复杂度要求：时间复杂度 $O(n \log n)$ ，空间复杂度 $O(n)$

示例1

输入

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

输出

说明

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

示例2

输入

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

输出

说明

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

备注:


在int范围内

算法知识视频讲解

害群之马

将活动开始时间写入一个列表starts，进行排序。

将活动结束时间写入一个列表ends，进行排序。

每次活动开始时，需要增加一个主持人上场，每次活动结束时候可以释放一个主持人。

所以按照时间先后顺序对starts进行遍历，每次有活动开始count++，每次有活动结束count--

在count最大的时候，即是需要主持人最多的时候

class Solution:
    def minmumNumberOfHost(self , n , startEnd ):
        starts=[]
        ends=[]
        for start,end in startEnd:
            starts.append(start);
            ends.append(end);
            
        starts.sort();
        ends.sort()
        
        i,j,count,res=0,0,0,0
        for time in starts:
            while(i<n and starts[i]<=time):
                i+=1
                count+=1
            while(j<n and ends[j]<=time):
                j+=1
                count-=1
            if res<count:
                res=count
        return res

编辑于 2021-06-14 23:18:19 回复(11)

Python 3

HHHChen77

python 问题类比于：同一时间最多重叠区间个数

class Solution:
    def minmumNumberOfHost(self , n , startEnd ):
        # 问题类比于 同一时间最多有多少个重叠区间
        # 分别统计活动的开始时间和结束时间
        start = []
        end = []
        for host in startEnd:
            start.append(host[0])
            end.append(host[1])
        start.sort()
        end.sort()
        # 统计同一时间的活动个数
        count = 0
        max_num = 0
        # 活动索引号
        i, j = 0, 0
        while i < n and j < n:
            # 有新活动开始
            if start[i] < end[j]:
                # 转到下个活动的开始时间作对比
                i += 1
                count += 1
                # 记录过程中的最大个数
                max_num = max(max_num, count)
            # 一个活动开始同时一个活动结束
            elif start[i] == end[j]:
                i += 1
                j += 1
            # 一个活动结束
            else:
                # 转到下个活动的结束时间作对比
                j += 1
                count -= 1
        # 返回最大值(同一时间最多有多少个活动在举行)
        return max_num

发表于 2021-07-24 15:17:12 回复(0)

码呆

是否等价于最大重叠区间问题？

发表于 2021-03-31 10:30:19 回复(6)

Java

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)

Python3

leeeeenas

from heapq import *

class Solution:
    def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int:
        # write code here
        pq = []
        startEnd.sort()
        for i in range(len(startEnd)):
            if len(pq)>0 and pq[0]<=startEnd[i][0]:
                heappop(pq)
            heappush(pq,startEnd[i][1])
        return len(pq)

发表于 2021-12-11 16:30:05 回复(0)

C++

Spectre_

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) {
        // 时间复杂度O(NlogN)，空间复杂度O(N)
        const int N = startEnd.size();
        int start[N], end[N];
        for (int i = 0; i < N; ++i) {
            start[i] = startEnd[i][0];
            end[i] = startEnd[i][1];
        }
        sort(start, start + n);
        sort(end, end + n);
        int j = 0, res = 0;
        for (int i = 0; i < N; ++i) {
            if (start[i] >= end[j]) ++j;
            else ++res;
        }
        return res;
    }
};

发表于 2022-10-19 16:47:48 回复(0)

Python 3

宫城良田z

class Solution:
    def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int:
        '''
        思路:
        解题思路
        正在进行的活动数量只会在 各活动开始或结束时变化.
        对正在进行的活动计数.
        '''
        # 首先由开始时间排序.
        startEnd.sort(key=lambda x:x[0])
        # 利用辅助数组，给每个活动的时间节点 标记start 或者 end.
        date = []
        for i in range(n):
            date.append([startEnd[i][0], 'start'])
            date.append([startEnd[i][1], 'end'])

        # 再给date排序
        date.sort(key=lambda x:x[0])

        # 计数, 从左至右遍历时间轴，start标签则num++, end则num--
        # res即当num最大时.
        res = 0; num = 0
        for d in date:
            if d[1] == 'start':
                num += 1
            elif d[1] == 'end':
                num -= 1
            res = max(num, res)
        return res

发表于 2022-05-21 20:46:41 回复(1)

C++

牛客612666370号

int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
    // write code here
    if (n == 1) return 1;
    map<int, int> cnt; // 有序
    for (auto& vec : startEnd) {
        ++cnt[vec[0]];
        --cnt[vec[1]];
    }
    int ans = 0;
    int curFreq = 0;
    for (auto& [_, freq] : cnt) {
        curFreq += freq;
        ans = max(ans, curFreq);
    }
    return ans;
}

差分数组

发表于 2022-08-06 19:06:32 回复(1)

Java

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)

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
        if(n==1)    return 1;
        if(n==0)    return 0;

        sort(startEnd.begin(),startEnd.end(), [](auto a, auto b){return (a[0]<b[0] || (a[0]==b[0] && a[1]<b[1]));});

        vector<long long> hoster;
        hoster.push_back(startEnd[0][1]);
        for(int i=1;i<n;i++){
            const int st=startEnd[i][0];
            int pos=-1;
            for(int j=0;j<hoster.size();j++){
                
                if(st>=hoster[j]){
                    pos = pos <0 ? j :pos;
                    pos = hoster[j]<hoster[pos]?j:pos;

                }
            }
            if(pos<0){
                hoster.push_back(startEnd[i][1]);
            }else{
                hoster[pos]=startEnd[i][1];
            }

            
        }
        return hoster.size();
        
    }
};

发表于 2024-09-21 15:24:39 回复(0)

Python3

ohayou123

class Solution:
    def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int:
        # write code here
        sort_startend = sorted(startEnd, key = lambda x:x[0])
        hosts =[]
        for it in sort_startend:
            if len(hosts)>0 and it[0] >= hosts[0]:
                heappop(hosts)
            heappush(hosts,it[1])
        return len(hosts)

发表于 2023-12-19 23:24:21 回复(0)

Java

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)

Python3

lun__

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算成功举办活动需要多少名主持人
# @param n int整型 有n个活动
# @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
# @return int整型
#
class Solution:
    def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int:
        # write code here
        ## 分离 开始时间和结束时间 start和end 
        start = [i[0] for i in startEnd]
        end = [i[1] for i in startEnd] 
        
        ## 排序 ：如果有交叉，则就需要加一个主持人 
        start.sort()  
        end.sort() 
        
        ## 使用一个循环控制两个数组 
        num = 0 
        end_time = 0 
        for i in range(n): 
            if start[i] >= end[end_time]: 
                end_time += 1   ## 无交叉情况，后移end_time  
            else: 
                num += 1     ## 有交叉，主持人数量 + 1 
        return num

发表于 2022-07-21 10:49:07 回复(2)

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(), [](auto& a, auto& b){
            if (a[0] == b[0]) return a[1] < b[1];
            return a[0] < b[0];
        });
        priority_queue<int, vector<int>, greater<int>> q;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            //当前开始时间大等于先前最早结束活动时间，不用添加新的主持人
            if (!q.empty() && startEnd[i][0] >= q.top()) {
                q.pop();
            }
            // 否则添加新的主持人主持活动
            else ++ans;
            // 添加或更新一个新的结束时间
            q.push(startEnd[i][1]);
        }
        return ans;
    }
};

发表于 2022-05-12 18:34:14 回复(0)

C++

duerduer冲啊

class Solution {
public:
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
        if(startEnd.empty()) return 0;
        sort(startEnd.begin(),startEnd.end(),[](vector<int>& a,vector<int>& b){
            if(a[0]!=b[0])
                return a[0] < b[0];//按照活动开始时间升序排序
            else
                return a[1] < b[1];//活动开始时间相等的，按照活动结束时间排序
        });
        //排序后，越靠前的活动都是尽早开始尽早结束
        //用小顶堆存储活动的结束时间，每当有一个新的任务来时，如果这个任务的开始时间>=堆顶的最早结束时间，则主持人数目不变，反之主持人+1
        priority_queue<int,vector<int>,greater<int> > min_q;
        min_q.push(startEnd[0][1]);
        for(int i=1;i<n;i++){
            if(startEnd[i][0]>=min_q.top()) {// 有空闲不需要增加主持人，当前主持人可以紧接着干下一个活
                min_q.pop();// 把上一个活出队，当前活会入队，即更新当前主持人赶下一个活的结束时间
            }
            min_q.push(startEnd[i][1]);// 如果跟上一个活时间重叠，就直接入队
        }
        return min_q.size();
    }
};

发表于 2022-05-12 12:30:48 回复(0)

Java

我难顶了

Comparator会溢出，我佛了

发表于 2022-03-25 18:21:32 回复(2)

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)

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
        map<int, int> mp;
        for (const auto& item : startEnd) {
            mp[item[0]]++;
            mp[item[1]]--;
        }
        int cur = 0;
        int ret = 0;
        for (const auto& item : mp) {
            cur += item.second;
            if (cur > ret) ret = cur;
        }
        return ret;
    }
};

发表于 2021-09-04 00:23:55 回复(0)

Python

爱上了老猫咪！

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 计算成功举办活动需要多少名主持人
# @param n int整型有n个活动
# @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
# @return int整型
#
class Solution:
def minmumNumberOfHost(self , n , startEnd ):
start=[]
end=[]
for i in range(n):
start.append(startEnd[i][0])
end.append(startEnd[i][1])

start.sort()
end.sort()
count=0
j=0
for i in range(n):
if start[i]>=end[j]:
j+=1
else:
count+=1
return count
# write code here

发表于 2021-05-13 11:21:38 回复(0)