Problem Description
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.
For example,
Given [[0, 30],[5, 10],[15, 20]], return 2.
Note: This problem is the extension of the former Meeting Room, which asks us whether we can attend all the meeting or not. The old Meeting Room problem asks us to check if there is a conflict between different meetings. However, this problem requires us to calculate the minimum number of meeting we need to arrange. Basic logic in behind is that if two meetings have time conflict, they have to be arranged in different rooms.
Solution
We basically browse through periods of the meetings, and map all starting time to 1 while all ending time to -1, so that we can decide whether we want to add 1 to our result, or to decrease 1 from the result.
- C++
int minMeetingRooms(vector<Interval>& intervals) {
vector<pair<int, int>> changes;
for (auto i : intervals) {
changes.push_back({i.start, 1});
changes.push_back({i.end, -1});
};
sort(changes.begin(), changes.end());
int rooms = 0, maxrooms = 0;
for (auto change : changes)
maxrooms = max(maxrooms, rooms += change.second);
return maxrooms;
}
TestCase:
std::vector<Interval> intervals;
for (int i=0; i<10; i++) {
Interval tmp;
tmp.start = (i+1)*2;
tmp.end = (i+2)*3;
cout << tmp.start << " - " << tmp.end << endl;
intervals.push_back(tmp);
}
int numRoom = sol.minMeetingRooms(intervals);
cout << numRoom << endl;