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

return

Given

`[[0, 30],[5, 10],[15, 20]]`

,return

`2`

.

Understand the problem:

Understand the problem:

A similar problem can be found:

http://buttercola.blogspot.com/2014/11/facebook-maximum-number-of-overlapping.html

The problem can be also transformed as max number of overlaps.

**Code (Java):**

/** * 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; } * } */ public class Solution { public int minMeetingRooms(Interval[] intervals) { if (intervals == null || intervals.length == 0) { return 0; } int len = intervals.length; int[] startTime = new int[len]; int[] endTime = new int[len]; for (int i = 0; i < len; i++) { Interval curr = intervals[i]; startTime[i] = curr.start; endTime[i] = curr.end; } // Sort the start and end time Arrays.sort(startTime); Arrays.sort(endTime); int activeMeetings = 0; int numMeetingRooms = 0; int i = 0; int j = 0; while (i < len && j < len) { if (startTime[i] < endTime[j]) { activeMeetings++; numMeetingRooms = Math.max(numMeetingRooms, activeMeetings); i++; } else { activeMeetings--; j++; } } return numMeetingRooms; } }

**Analysis:**

Sorting two arrays take O(nlogn) time. Compare takes O(n) time. So the overall time complexity is still bounded by O(nlogn).

**An alternative solution using Priority Queue:**

An alternative solution is to use a priority queue to store the end times. Then we sort the intervals according to its start time. We iterate through the intervals. If the current start time is less than the earliest end time in the pq, numRooms++. Else, remove the earliest time from the pq. For each iteration, we also need to offer the current ending time into the pq.

**Code (Java):**

/** * 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; } * } */ public class Solution { public int minMeetingRooms(Interval[] intervals) { if (intervals == null || intervals.length == 0) { return 0; } Arrays.sort(intervals, new IntervalComparator()); PriorityQueue<Integer> pq = new PriorityQueue<>(); int numRooms = 1; pq.offer(intervals[0].end); for (int i = 1; i < intervals.length; i++) { if (intervals[i].start < pq.peek()) { numRooms++; pq.offer(intervals[i].end); } else { pq.poll(); pq.offer(intervals[i].end); } } return numRooms; } public class IntervalComparator implements Comparator<Interval> { @Override public int compare(Interval a, Interval b) { return a.start - b.start; } } }

There are many specialized conference and meeting room out there which are in high demand. This is because of the aura and atmosphere in the Seattle convention center. You must visit their site to get a sneak peek of the rooms.

ReplyDeletea conference room can seat a maximum of 85 people.?

ReplyDeletechristmas party venues liverpool