LeetCode 253. Meeting Rooms II

Question

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Example 1:

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

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: 1

Constraints:

• 1 <= intervals.length <= 104
• 0 <= starti < endi <= 106

Source: https://leetcode.com/problems/meeting-rooms-ii/

Solution

We can simulate the schedule of meeting rooms by a min heap of ends of intervals. Because when a new meeting comes in, we only need to compare its start time with the end time of the earliest ending meeting, and decide whether we should add one more room. Note that in the following implementation, we poll at most one element from the heap per loop, rather than polling all terminated meetings, because we choose return the size of the heap as the result.

Logically chronological ordering solution is further optimized, though its time complexity is the same heap-based solution, O(nlog(n)). The idea is break the relationship between start and end. We sort starts and ends separately, and use two pointers to traverse them. We can still get the correct result because we do not care about which meeting ends and makes a room spare, but the timepoint of the end. One evidence is that in the heap-based solution, we only stores ends of intervals in the heap.

// heap, O(nlog(n))
public int minMeetingRooms(int[][] intervals) {
    if (intervals.length == 0) {
        return 0;
    }
    // sort intervals by the start in ascending order
    Arrays.sort(intervals, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[0] - o2[0];
        }
    });
    // min heap of end of interval
    PriorityQueue<Integer> endMinHeap = new PriorityQueue<>(intervals.length, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2;
        }
    });
    endMinHeap.add(intervals[0][1]);
    for (int i = 1; i < intervals.length; i++) {
        int[] curr = intervals[i];
        // try to find a free room
        if (curr[0] >= endMinHeap.peek()) {
            endMinHeap.poll();
        }
        endMinHeap.add(curr[1]);
    }
    return endMinHeap.size();
}

// Chronological Ordering, O(nlog(n))
public int minMeetingRooms2(int[][] intervals) {
    int len = intervals.length;
    if (len == 0) {
        return 0;
    }
    int[] starts = new int[len];
    int[] ends = new int[len];
    for (int i = 0; i < len; i++) {
        starts[i] = intervals[i][0];
        ends[i] = intervals[i][1];
    }
    // sort respectively by ascending order
    // we want to know if there is an empty room at a certain point in time,
    // but don't care which meeting room it is
    Arrays.sort(starts);
    Arrays.sort(ends);
    int startIndex = 0, endIndex = 0;
    int numRoom = 0;
    while (startIndex < len && endIndex < len) {
        if (starts[startIndex] >= ends[endIndex]) {
            startIndex++;
            endIndex++;
        } else {
            startIndex++;
            numRoom++;
        }
    }
    return numRoom;
}