- 题目描述:
- 题目链接:
-视频讲解链接B站视频讲解
- 复杂度分析:
- 代码:
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 };