สมมติว่ามีอาร์เรย์ของช่วงเวลาการประชุม มีเวลาเริ่มและสิ้นสุด [[s1,e1],[s2,e2],...] และแต่ละคู่สอดคล้องกับกฎ (si < ei) เราต้องหาจำนวนห้องประชุมขั้นต่ำที่จำเป็น
เช่น ถ้าอินพุทเป็น [[0, 30], [5, 10], [15, 20]] ผลลัพธ์จะเป็น 2
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้ −
กำหนด priority queue pq
เรียงลำดับอาร์เรย์ intervals
ret := 0
ลูป i := 0 ถึงขนาดของ intervals-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
