253. Meeting Rooms II

Description

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.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: [[0, 30], [5, 10], [15, 20]]

Output: 2

Example 2

Input: [[7, 10], [2, 4]]

Output: 1

Solutions

Solution 1

/**
 * Time complexity : O(NlogN).
 * Space complexity : O(N)
 */

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if(intervals == null) return 0;
        Arrays.sort(intervals, 
                    Comparator.comparing((int[] interval) -> interval[0]));
        
        PriorityQueue<Integer> heap = new PriorityQueue();
        int meetingRooms = 0;
        
        for(int[] interval: intervals) {
            if(heap.isEmpty()) {
                meetingRooms++;
            } else {
                if(interval[0] >= heap.peek()) {
                    heap.poll();
                } else {
                    meetingRooms++;
                }
            }
            heap.offer(interval[1]);
        }
        return meetingRooms;
    }
}

Solution 2

/**
 * Time complexity : O(NlogN).
 * Space complexity : O(N)
 */

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if(intervals == null || intervals.length == 0) return 0;
        
        int n = intervals.length;
        int[] startTimes = new int[n];
        int[] endTimes = new int[n];
        
        for(int i = 0; i < n; i++) {
            startTimes[i] = intervals[i][0];
            endTimes[i] = intervals[i][1];
        }
        
        Arrays.sort(startTimes);
        Arrays.sort(endTimes);
        
        int meetingRooms = 0,
            endTimeIdx = 0;
        
        for(int i = 0; i < n; i++) {
            if(startTimes[i] >= endTimes[endTimeIdx]) {
                endTimeIdx++;
            } else {
                meetingRooms++;
            }
        }
        
        return meetingRooms;
    }
}

Follow up