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

Algorithm

A typical Chronological Ordering. We will need total order or both start and ends.

While we sort start and order individually. It's fine because : we don't really care about which meeting ends and we only need to know there is a meeting ends and room are available.

So the algorithm is like :

1. We sort all the starts and ends separately
2. Loop the starts and ends at the same time, start from ends
3. If a start is before current end, then we know they are conflict and needs one more meeting room, so res++;
4. Else, which is the start is after the end, they are not conflict so one room is enough and we don't need another room. But current end becomes next end.(current start is bigger than previous end and thus we no longer concern that end)
5. Return res;

Implementation

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int n = intervals.length;
        int res = 0;
        int[] starts = new int[n];
        int[] ends = new int[n];
        int index = 0;
        for (int[] interval : intervals) {
            starts[index] = intervals[index][0];
            ends[index] = intervals[index++][1];
        }
        Arrays.sort(starts);
        Arrays.sort(ends);

        for (int i = 0, j = 0; i < n; i++) {
            if (starts[i] < ends[j]) {
                res++;
            } else {
                j++;
            }
        }
        return res;
    }
}