[LeetCode] Meeting Rooms II

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 };