[LeetCode] 253. Meeting Rooms II

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

The minimum required meeting rooms equals to the maximum meeting happen in parallel.

- Solution 1. Use counter to count the meetings happen in parallel.

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return a[0] < b[0] ? -1 : 1;
            }
            
            return a[1] < b[1] ? -1 : 1;
        });
        for (int i = 0; i < intervals.length; i++) {
            pq.offer(new int[]{intervals[i][0], 1});
            pq.offer(new int[]{intervals[i][1], -1});
        }
        
        int count = 0;
        int result = 0;
        
        while (!pq.isEmpty()) {
            count += pq.poll()[1];
            result = Math.max(result, count);
        }
        
        return result;   
    }
}

- Solution 2. Use priority queue to save the meeting end time. The size of priority queue equals to the number of meetings happen in parallel.

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] < b[0] ? -1 : 1;
            }
            
            return a[1] < b[1] ? -1 : 1;
        });
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int result = 0;
        
        for (int i = 0; i < intervals.length; i++) {
            while (!pq.isEmpty() && pq.peek() <= intervals[i][0]) {
                // the last meeting has ended.
                // remove it from the queue
                pq.poll();
            }
            
            pq.offer(intervals[i][1]);
            result = Math.max(result, pq.size());
        }
        
        return result;
    }
}