252/253. Meeting Rooms I/II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei),
1. determine if a person could attend all meetings.
2.find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.
1. determine if a person could attend all meetings.
思路: 求是否能参加所有的会议。 也就是找一个会议的start跟其他会议的end是否有冲突.
复杂度: time:O(nlogn),space:O(1)

/**
 * 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 boolean canAttendMeetings(Interval[] intervals) {
        if (intervals == null || intervals.length == 0)
            return true;
        Arrays.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval i1, Interval i2) {
                return i1.start - i2.start;
            }
        });    
        int end = intervals[0].end;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i].start < end) { // 会议开始时间小于最晚结束时间
                return false;
            }
            end = Math.max(end, intervals[i].end);
        }
        return true;
    }
}

2.find the minimum number of conference rooms required.
思路: 求总共需要多少个会议室, 贪心的思路,这里的trick是借助mini heap,同样存每个会议的结束时间,heap中总是返回最早结束的会议。我们遍历会议的时候,找当前会议的start跟heap中最早的结束的会议的end进行比较,也就是当mtg2.start )heap.peek(也就是最早结束meeting的end), 那么我们可以把当前meeting安排到这个房间,这时把heap.poll(),存入当前meeting的end。 否则的话,开辟一个新的房间来放,也就是直接把当前meeting的end放入heap。 最后返回heap.size 就是需要的房间.
复杂度: time O(nlogn), space O(1)

/**
 * 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<Interval>(){
            public int compare(Interval v1, Interval v2) {
                return v1.start - v2.start;
            }
        });    
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        heap.add(intervals[0].end);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i].start >= heap.peek()) {// 下一个meeting的start晚与或者等于上一个meeting的end.
                heap.poll();
            }
            heap.add(intervals[i].end);
        }
        return heap.size();
    }
}
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