253. 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.

Example 1:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2

Example 2:

Input: [[7,10],[2,4]]

Output:1

Thoughts:

1. Sort the interval by the start time

2. Using the priority queue to use the end time as the order to sort the used classroom

3. pop the earliest ending meeting room, check if the time ends earlier than the start time of current class being scheduled, if earlier, merge the interval by setting the poped intervals'end time as the current intervals' scheduled end time, push the current interval into pq as making a new room.

4. return the size of the pq as the result

Code

/**
 * 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;
        // sort the arrays by start time
        Arrays.sort(intervals, new Comparator<Interval>(){
           @Override
            public int compare(Interval a, Interval b) {return a.start - b.start;}
        });
        // sort the heap by end time (scheduled meeting)
        PriorityQueue<Interval> pq = new PriorityQueue<Interval>(intervals.length, new Comparator<Interval>(){
           @Override 
            public int compare (Interval a, Interval b) {return a.end - b.end;}
        });

        pq.offer(intervals[0]);

        for(int i = 1; i < intervals.length; i++){
            Interval earliest = pq.poll();
            Interval curInterval = intervals[i];

            if(earliest.end <= curInterval.start){
                earliest.end = curInterval.end; // merge (use the same room)
            }
            else {
                pq.offer(curInterval); // schedule a new room
            }

            pq.offer(earliest);
        }

        return pq.size();
    }
}

Python

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):  
    def minMeetingRooms(self, intervals):
        events = [(it.start, +1) for it in intervals] + [(it.end, -1) for it in intervals]
        events = sorted(events)

        rooms = 0
        max_concurrent = 0
        for t, inc in events:
            rooms += inc
            max_concurrent = max(max_concurrent, rooms)

        return max_concurrent