Meeting Room I

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

For example

Given [[0, 30],[5, 10],[15, 20]],
return false.

思路

与merge overlapping interval那个题目一致

1. 先根据会议的时间顺序对序列进行排序（先对起始时间排序，如果起始时间一致，则根据结束时间排序）
2. 遍历序列，看是否有会议时间是冲突的，如果一旦有冲突，则直接返回false，无法参与所有会议。
3. 如果遍历完成后都没有冲突，则返回true。

/**
 * 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 boolean canAttendMeetings(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) {
            return true;
        }
        
        //先根据会议的时间顺序对序列进行排序（先对起始时间排序，如果起始时间一致，则根据结束时间排序）
        Arrays.sort(intervals, (o1, o2)-> o1.start != o2.start ? o1.start - o2.start : o1.end - o2.end);
        
        Interval pre = intervals[0];
        
        //遍历序列，看是否有会议时间是冲突的，如果一旦有冲突，则直接返回false，无法参与所有会议
        for (int i = 1; i < intervals.length; i++) {
            Interval cur = intervals[i];
            
            if (cur.start < pre.end) {
                return false;
            } else {
                pre = cur;
            }
        }
        
        return true;
    }
}

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.

思路

1. 用miniheap来存有冲突的会议室的结束时间
   PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
2. 遍历所有会议时间，根据当前会议的开始时间，和最小堆中第一个结束时间比较。（因为会议事先排过序，且miniheap是按照从小到大的顺序来排列的）
   • 如果冲突，说明需要多一个房间，那么在miniheap中推入当前这个会议的结束时间。
   • 如果不冲突，则说明当前的会议，可以跟miniheap的第一个结束时间的会议公用一个会议室。 那么此时把miniheap堆顶的结束时间弹出，再把当前的结束时间压入栈（因为共用会议室，所以更新成最新的结束时间即可）

/**
 * 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) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }
        
        // 1 sort
        Arrays.sort(intervals, (o1, o2) -> o1.start != o2.start ? o1.start - o2.start : o1.end - o2.end);
        
        //2. PriorityQueue存所有已经结束的会议的完成时间
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
        
        //3.遍历找到需要几个会议室
        int heapTop = intervals[0].end;
        queue.offer(heapTop);
        
        for (int i = 1; i < intervals.length; i++) {
            //如果冲突，说明需要多一个房间，那么在queue中推入当前这个会议的结束时间
            if (!queue.isEmpty() && intervals[i].start < queue.peek()) {
                queue.offer(intervals[i].end);
            } else { // 如果不冲突，则说明当前的会议，可以跟miniheap的第一个结束时间的会议公用一个会议室
                       // 那么此时把miniheap堆顶的结束时间弹出，再把当前的结束时间压入栈（因为共用会议室，所以更新成最新的结束时间即可）
                queue.poll();
                queue.offer(intervals[i].end);
            }       
            }
        
        return queue.size();
        
        
    }
}