Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (s_i < e_i), 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

 

 

Solution:

Sorting the input intervals by the start time.

Creating a minHeap, put the first interval in it.

Traversing the input intervals from the second interval to the end.

if (the end time of the top of the minHeap) is small or equal to (the start time of the next input interval), replace the top minHeap interval to next input interval.

else, just add the next input interval to the minHeap.

At the end, return the size of minHeap.

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        
        Arrays.sort(intervals, (a, b) -> (a[0] - b[0]));
        
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> (a[1] - b[1]));
        minHeap.add(intervals[0]);
        
        for (int i = 1; i < intervals.length; i++) {
            if (minHeap.peek()[1] <= intervals[i][0]) {
                minHeap.poll();
                minHeap.add(intervals[i]);
            } else {
                minHeap.add(intervals[i]);
            }
        }
        
        return minHeap.size();
    }
}

Time complexity: O(n log(n)), sorting the input intervals and minHeap operation.

Space complexity: O(n).