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.
The idea is to group those non-overlapping meetings in the same room and then count how many rooms we need. You may refer to this link.
The code is as follows.
1 class Solution { 2 public: 3 int minMeetingRooms(vector<Interval>& intervals) { 4 sort(intervals.begin(), intervals.end(), compare); 5 vector<vector<Interval>> rooms; 6 int n = intervals.size(); 7 for (int i = 0; i < n; i++) { 8 int idx = findNonOverlapping(rooms, intervals[i]); 9 if (rooms.empty() || idx == -1) 10 rooms.push_back({intervals[i]}); 11 else rooms[idx].push_back(intervals[i]); 12 } 13 return (int)rooms.size(); 14 } 15 private: 16 static bool compare(Interval& interval1, Interval& interval2) { 17 return interval1.start < interval2.start; 18 } 19 int findNonOverlapping(vector<vector<Interval>>& rooms, Interval& interval) { 20 int n = rooms.size(); 21 for (int i = 0; i < n; i++) 22 if (interval.start >= rooms[i].back().end) 23 return i; 24 return -1; 25 } 26 };
Update: for each group of non-overlapping intervals, we just need to store the last added one instead of the full list. So we could use a vector<Interval> instead of vector<vector<Interval>> in C++. The code is now as follows.
1 class Solution { 2 public: 3 int minMeetingRooms(vector<Interval>& intervals) { 4 sort(intervals.begin(), intervals.end(), compare); 5 vector<Interval> rooms; 6 int n = intervals.size(); 7 for (int i = 0; i < n; i++) { 8 int idx = findNonOverlapping(rooms, intervals[i]); 9 if (rooms.empty() || idx == -1) 10 rooms.push_back(intervals[i]); 11 else rooms[idx] = intervals[i]; 12 } 13 return (int)rooms.size(); 14 } 15 private: 16 static bool compare(Interval& interval1, Interval& interval2) { 17 return interval1.start < interval2.start; 18 } 19 int findNonOverlapping(vector<Interval>& rooms, Interval& interval) { 20 int n = rooms.size(); 21 for (int i = 0; i < n; i++) 22 if (interval.start >= rooms[i].end) 23 return i; 24 return -1; 25 } 26 };
