Meeting Rooms II

Problem

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.

Solution

PriorityQueue Solution

class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) return 0;
        Arrays.sort(intervals, (a, b) -> a.start - b.start);
        PriorityQueue<Interval> pq = new PriorityQueue<>(intervals.length, (a, b) -> a.end - b.end);
        int res = 0;
        for (Interval interval : intervals) {
            while (!pq.isEmpty() && interval.start >= pq.peek().end) pq.poll();
            pq.offer(interval);
            res = Math.max(pq.size(), res);
        }
        return res;

    }
}

starts and ends Solution

class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) return 0;
        int len = intervals.length;
        int[] starts = new int[len], ends = new int[len];
        for (int i = 0; i < len; i++) {
            starts[i] = intervals[i].start;
            ends[i] = intervals[i].end;
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        int rooms = 0, endIndex = 0;
        for (int i = 0; i < len; i++) {
            if (starts[i] < ends[endIndex]) rooms++;
            else endIndex++;
        }
        return rooms;
    }
}

Analysis

The first solution uses PriorityQueue<Interval> as a room schedule table in real life
It stores the rooms that having meeting at the time
Hence we just need to return the possible maximum size of pq
We sort the given intervals by their starts and sort the pq by their ends
For each new meeting, we first check if there is any room in pq
If so, we check if the current meeting start is >= pq.peek()
If so, we know we can arrange the current meeting to that room in pq
Therefore, we call pq.poll() and offer() current meeting later, and we update the res with maximum pq.size()
The second solution stores all the starts and ends in two arrays and sorts them respectively
We have a endIndex, which represents first ends meeting room
Then we simply loop through the intervals and see if current meeting's start is < ends[endIndex]
If so, we have to open a new room, and we don't need to update endIndex because ends are already sorted and ends[endIndex] is currently smallest
If starts[i] >= ends[endIndex], then we have to move endIndex++ because we put current meeting to previous meeting room, hence the endIndex needs to be updated by next meeting's end