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.

Solution1:

Sorting two arrays take O(nlogn) time. Compare takes O(n) time. Run time complexity is O(nlogn), space complexity is O(n).

/**
 * 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[] start = new int[intervals.length];
        int[] end = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            start[i] = intervals[i].start;
            end[i] = intervals[i].end;
        }
        
        Arrays.sort(start);
        Arrays.sort(end);
        
        int activeMeeting = 0;
        int minMeeting = 0;
        int i = 0;
        int j = 0;
        while (i < intervals.length && j < intervals.length) {
            if (start[i] < end[j]) {
                activeMeeting++;
                minMeeting = Math.max(activeMeeting, minMeeting);
                i++;
            } else {
                activeMeeting--;
                j++;
            }
        }
        
        return minMeeting;
    }
}

Solution2: Priority queue, Comparator
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.
Reference: http://buttercola.blogspot.com/2015/08/leetcode-meeting-rooms-ii.html

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