[LeetCode] 253. Meeting Rooms II

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.

Thought process:

The idea is to first sort the array based on start time, so we can examine the meetings as they take place in order (and be greedy). 

Suppose we have three meetings: [0, 30], [5, 10], and [15, 20] in sorted order. When we see the second meeting, we check if its start time is later than the first meeting's end time. It's not, so we need another room. We then compare the third meeting's start time with the minimum of first two meetings' end times. If there is a meeting that ends before the third meeting starts, then we don't need another room.

So as we iterate through the array, we need to store each meeting's end time and get the minimum quickly. Min heap is a natural choice.

Solution (C++):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

/** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */ class Solution { public: int minMeetingRooms(vector<Interval>& intervals) { if (intervals.size() == 0) { return 0; } sort(intervals.begin(), intervals.end(), [](const Interval& i1, const Interval& i2) -> bool { return i1.start < i2.start; }); priority_queue<int, vector<int>, greater<int>> heap; int rooms = 0; heap.push(intervals[0].end); rooms++; for (int i = 1; i < intervals.size(); i++) { if (intervals[i].start < heap.top()) { rooms++; } else { heap.pop(); } heap.push(intervals[i].end); } return rooms; } };

Java:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

/** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */ class Solution { public int minMeetingRooms(Interval[] intervals) { Arrays.sort(intervals, (a, b) -> a.start - b.start); PriorityQueue<Integer> heap = new PriorityQueue<>(); for (Interval i : intervals) { if (!heap.isEmpty() && i.start >= heap.peek()) { heap.poll(); } heap.offer(i.end); } return heap.size(); } }

Time complexity:
Sorting takes O(nlogn). Offering to min heap takes O(logn) so the for loop takes O(nlogn). The overall time complexity is O(nlogn).