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

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        
    }
}

Problem Clarification

In the first example, [5, 10] and [15, 20] do not overlap, so we can accommodate those two in a single room. However [0, 30] overlaps with other two, so we need 1 room for [0, 30], thus in total 2 rooms are needed. Lets assume, if we have [a, b] and [b, c] where a < b, we can accommodate them in a single room, though the second meeting folks would be entering when first meeting folks are exiting.

Idea - 1

If we want to place the meeting, it helps to arrange them in increasing order of start time - if one meeting starts in the morning and one starts in the evening, naturally the morning one needs to be accommodated first. Say we scheduled the meeting that starts earliest in a room. Now the meeting that starts next, if it starts no earlier than when the first meeting ends, we can reuse the room, otherwise we need another room. So, to find out if an earlier room can be reused, it helps to know which of the earlier rooms become empty first, i.e. which of the earlier room's end time comes first (we use a minheap with comparison on end times). If we cannot reuse that room for the current meeting, no other of the earlier rooms can be reused, we need a new room. Because current meeting starts later than every other previously seen meeting. Sorting takes time and the minheap operations take time. So overall time and space .

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int n = intervals.length;
        if(n < 2)
        {
            return n;
        }
        
        Arrays.sort( intervals, new Comparator<int[]>()
                    {
                        public int compare(int[] a, int[] b)
                        {
                            return a[0]-b[0];
                        }
                    });
        
        PriorityQueue<int[]> minq = new PriorityQueue<int[]>(new Comparator<int[]>()
                                                             {
                                                                 public int compare(int[] a, int[] b)
                                                                 {
                                                                     return a[1]-b[1];
                                                                 }
                                                             });
        
        minq.offer(intervals[0]);
        for(int i = 1; i < n; ++i)
        {
            int[] curr = intervals[i];
            int[] earliestFree = minq.poll();
            
            if(curr[0] >= earliestFree[1]) // reuse
            {
                // update how long it will be occupied
                earliestFree[1] = Math.max(earliestFree[1], curr[1]);
            }
            else // needs a separate room
            {
                minq.offer(curr);
            }
            
            minq.offer(earliestFree);
        }
        
        return minq.size();
    }
}


Runtime: 8 ms, faster than 53.61% of Java online submissions for Meeting Rooms II.
Memory Usage: 37.9 MB, less than 74.91% of Java online submissions for Meeting Rooms II.