2.1 Meeting Rooms II 253

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]],
return2.

Hint

Method

To understand why it works, first let’s define two events:
Meeting Starts
Meeting Ends

Next, we acknowledge three facts:
The numbers of the intervals give chronological orders
When an ending event occurs, there must be a starting event has happened before that, where “happen before” is defined by the chronological orders given by the intervals
Meetings that started which haven’t ended yet have to be put into different meeting rooms, and the number of rooms needed is the number of such meetings

So, what this algorithm works as follows:

for example, we have meetings that span along time as follows:

|
_____
|
      |
______
|
|
________
|
        |
_______
|

Then, the start time array and end time array after sorting appear like follows:

||
||
     |
|
|
|

Initially,endsItrpoints to the first end event, and we moveiwhich is the start event pointer. As we examine the start events, we’ll find the first two start events happen before the end event thatendsItrpoints to, so we need two rooms (we magically created two rooms), as shown by the variable rooms. Then, asipoints to the third start event, we’ll find that this event happens after the end event pointed byendsItr, then we incrementendsItrso that it points to the next end event. What happens here can be thought of as one of the two previous meetings ended, and we moved the newly started meeting into that vacant room, thus we don’t need to increment rooms at this time and move both of the pointers forward.
Next, becauseendsItrmoves to the next end event, we’ll find that the start event pointed byihappens before the end event pointed byendsItr. Thus, now we have 4 meetings started but only one ended, so we need one more room. And it goes on as this.

Time & Space

O(n + nlogn)

Code

`public class Solution {
`

`    public int minMeetingRooms(Interval[] intervals) {
`

`           if (intervals == null || intervals.length == 0){
`

`               return 0;
`

`           }
`

`           
`

`           int len = intervals.length;
`



`           int[] starts = new int[len];
`

`           int[] ends = new int[len];
`

`           
`

`           for (int i = 0; i < len; i++){
`

`                starts[i] = intervals[i].start;
`

`                ends[i] = intervals[i].end;
`

`           }
`

`           
`

`           Arrays.sort(starts);
`

`           Arrays.sort(ends);
`

`           
`

`           int rooms = 0;
`

`           int endTime = 0;
`

`           
`

`           for (int i = 0; i < len; i++){
`

`                if (starts[i] < ends[endTime]){
`

`                    rooms++;
`

`                } else {
`

`                    endTime++;
`

`                }
`

`           }
`

`           return rooms;
`

`    }
`

`}`