一、分析题目
把区间按照左端点排序,然后搞个堆:
- 先把第⼀个区间的右端点加⼊到堆中。
- 遍历后⾯的区间,分情况讨论:(1)如果左端点大于等于堆顶元素,能接在后面,干掉堆顶,然后把这个区间的右端点加⼊堆。(2)否则,只能再来⼀个人,只把这个区间的右端点加⼊堆。
- 最后堆的大小就是需要的⼈数
二、代码
//O(NlogN) class Solution { public: int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) { sort(startEnd.begin(), startEnd.end()); priority_queue<int, vector<int>, greater<int>> heap; // 创建⼀个⼩根堆 heap.push(startEnd[0][1]); // 先把第⼀个区间放进去 for(int i = 1; i < n; i++) // 处理剩下的区间 { int a = startEnd[i][0], b = startEnd[i][1]; if(a >= heap.top()) // 没有重叠 { heap.pop(); heap.push(b); } else // 有重叠 { heap.push(b); // 重新安排⼀个⼈ } } return heap.size(); } };
三、反思与改进
对优先级队列掌握的还不够熟悉,导致想不起可以用这个容器来解决问题。因为主持人可以主持多场活动,所以不能直接遍历比较。