253. Meeting Rooms II

/**

 * 253. Meeting Rooms II

 * 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

*/

This is a very common question and has a very easy approach.

See my solution to the problem here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/search/MeetingRooms.java

The logic has below steps:

1. Sort the meetings by start time. This is done so that you can iterate through the meetings and find whether a previous meeting is ending before this meeting starts.
2. Add the meeting end time to priority queue. If priority queue’s top is before the current meeting start then remove it from the priority queue. Else increase the number of meeting rooms needed by 1.

public int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int i = 0; i < intervals.length; i++) {
        if (!minHeap.isEmpty() && minHeap.peek() <= intervals[i][0]) {
            minHeap.poll();
        } else {
            roomsInUse++;
        }
        minHeap.add(intervals[i][1]);
    }
    return roomsInUse;
}