Meeting Rooms II

Leave a comment

December 18, 2016 by oneOokay

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.


用什么来表示”会议室”?怎么计算个数?把会议室抽象为一个时间段就可以了。

  • 首先把所有的会议按照开始的时间进行排序。
  • 用一个最小堆 Min Heap(按会议结束的时间),里面存Intervals,每一个Interval就代表一个会议室,Interval的时间段代表这个会议室开会的时间段。
  • MinHeap 的top就是第一个开完会的会议室。接下来的一个会议,如果它的开始时间晚于minHeap top的会议室结束时间,那么该会议室就可以被继续用来开下一个会,同时更新这个会议室的结束时间;如果接下来的会议开始时间早于min Heap top的会议结束时间(产生overlapping了),那么此时所有所有的会议室都是unavailable的(因为是一个以开完会时间排序的一个minHeap)此时就需要再加入一个新的会议室来开这个会。
  • 所以整个MinHeap的size就是所需要的会议室的个数。

然后还有一个“super easy java solution”, 在后面.

/**
 * 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 Comparator(){//不要漏了T
           public int compare(Interval i1, Interval i2){//compare小写
               if (i1 != i2){
                   return i1.start - i2.start;
               }
               return 0;
           } 
        });
        
        Queue queue = new PriorityQueue(intervals.length, 
new Comparator(){
            public int compare(Interval i1, Interval i2){
                if (i1 != i2){
                    return i1.end - i2.end;
                }
                return 0;
            }
        });
        queue.offer(intervals[0]);
        for (int i = 1; i < intervals.length; i ++){
            Interval meeting = queue.poll();
            if (meeting.end <= intervals[i].start){
                meeting.end = intervals[i].end;
            }else {
                queue.offer(intervals[i]);
            }
            queue.offer(meeting);
        }
        return queue.size();
    }
}

看上去超级简单的解法:

把Interval的start和end分别存到两个int array里面,从小到大排列,然后从第一个元素开始遍历.

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;
 }
//这里并不需要考虑哪个start对应哪个end
 Arrays.sort(starts);
 Arrays.sort(ends);
 int room = 0; //房间个数
//这个之后用来计算ends[pre]:代表目前目前正在进行的会议中最先结束的那个会议的结束时间
 int pre = 0; //初始化:会议中第一个结束的会
 for (int i = 0; i < len; i ++){
每一个start对应一个会;初始对于每一个会,理论上我们都要一个meeting room给它
所以先+1.
 room ++;
看一下当前要开始的这个会议,与目前最早结束的会议时间对比.
如果当前要开始的会议时间大于最早结束的会议,那么说明当前的会议可以用当前最早结束会议的
房间,所以原计划的房间数字减掉1.
同时,新的会议开始了,那么之前在那个房间的会议就结束了,于是pre指针向后移.我们就要考虑下一个
最早结束的会议的房间了.
 if (starts[i] >= ends[pre]){
 room --;
 pre ++;
 }
 }
 return room;//返回最终的房间数.
 }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: