leetcode算法题--会议室★★_leetcode 会议室 权重

题目来源于leetcode第252号问题：会议室。

题目描述：

给定一个会议时间安排的数组，每个会议时间都会包括开始和结束的时间 [[ s1 , e1 ] ，[ s2 , e2 ]，…] (si < ei) ，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。

示例 1:

输入: [[0, 30],[5, 10],[15, 20]]
输出: 2
1
2

示例 2:

输入: [[7,10],[2,4]]
输出: 1
1
2

题目解析

使用贪心算法，按开始时间排序，将第一个会议结束时间加入小顶堆，若后一个会议时间晚于此堆顶时间，则将堆顶弹出。

bool mySort(vector<int> &a,vector<int> &b){
	return (a[0]==b[0]&&a[1]<b[1])||a[0]<b[0];
}
int minMeetingRooms(vector<vector<int>> intervals){
	sort(intervals.begin(),intervals.end(),mySort);//按会议开始时间排序
	priority_queue<int,vector<int>,greater<int>> q;
	q.push(intervals[0][1]);//将第一个会议结束时间加入队列
	for(int i=1;i<intervals.size();i++){//从第i个会议开始比较
		if(q.top()<=intervals[i][0]){//若队列头部小于等于第i个会议的开始时间，则弹出
			q.pop();
		}
		q.push(intervals[i][1]);//将第i个会议的结束时间加入队列
	}
	return q.size();//返回队列的大小
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

原文链接：https://www.cxyxiaowu.com/373.html