一、分析题目
把区间按照左端点排序，然后搞个堆：
- 先把第⼀个区间的右端点加⼊到堆中。
- 遍历后⾯的区间，分情况讨论：（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(); } };
三、反思与改进
对优先级队列掌握的还不够熟悉，导致想不起可以用这个容器来解决问题。因为主持人可以主持多场活动，所以不能直接遍历比较。
