資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究C++ 中的會議室 II
假設有一個會議時間間隔陣列。有兩個起始和結束時間 [[s1,e1],[s2,e2],...]，並且每對都滿足規則 (si < ei)，我們必須找到所需的最小會議室數量。
因此，如果輸入如下 [[0, 30], [5, 10], [15, 20]]，則輸出將為 2。
要解決這個問題，我們將按照以下步驟進行 −
定義一個優先順序佇列 pq
對 intervals 陣列進行排序
ret := 0
對初始化 i := 0，當 i < intervals 的大小，更新 (i 增加 1)，執行 −
while (pq 不為空並且 pq 的頂部元素 <= intervals[i, 0]) 執行 −
從 pq 中刪除元素
將 intervals[i] 插入 pq
ret := ret 和 pq 大小的最大值
返回 ret
示例
讓我們看看以下實現，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
struct Comparator{
bool operator()(vector <int<& a, vector <int<& b){
return !(a[1] < b[1]);
}
};
class Solution {
public:
static bool cmp(vector <int< a, vector <int< b){
return (a[1] < b[1]);
}
int minMeetingRooms(vector<vector<int<>& intervals) {
priority_queue<vector<int<, vector<vector<int< >, Comparator> pq;
sort(intervals.begin(), intervals.end());
int ret = 0;
for (int i = 0; i < intervals.size(); i++) {
while (!pq.empty() && pq.top()[1] <= intervals[i][0])
pq.pop();
pq.push(intervals[i]);
ret = max(ret, (int)pq.size());
}
return ret;
}
};
main(){
vector<vector<int<> v = {{0, 30}, {5, 10}, {15, 20}};
Solution ob;
cout << (ob.minMeetingRooms(v));
}輸入
{{0, 30}, {5, 10}, {15, 20}}輸出
2
更新時間:18-11-2020
903 次檢視
廣告