Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Problem Challenge 1: Minimum Meeting Rooms

Problem Statement

Given a list of intervals representing the start and end time of ‘N’ meetings, find the minimum number of rooms required to hold all the meetings.

Example 1:

Meetings: [[1,4], [2,5], [7,9]]
Output: 2
Explanation: Since [1,4] and [2,5] overlap, we need two rooms to hold these two meetings. [7,9] can occur in any of the two rooms later.

Example 2:

Meetings: [[6,7], [2,4], [8,12]]
Output: 1
Explanation: None of the meetings overlap, therefore we only need one room to hold all meetings.

Example 3:

Meetings: [[1,4], [2,3], [3,6]]

.....

.....

.....

Like the course? Get enrolled and start learning!
C

CaptainKidd

· 3 years ago

Why change up the style of the answer in such a drastic way vs eariler? It only adds to confusion with no benefit.

Here's something similar to the examples we've seen this far. Please note similarity in structure to sliding window.

Arrays.sort(intervals, (a,b)->Integer.compare(a[0], b[0])); PriorityQueue minHeap = new PriorityQueue(intervals.length, (a, b) -> Integer.compare(a[1], b[1])); int minRooms = 0; for(int[] interval : intervals){ if(!minHeap.isEmpty() && interval[0]>=minHeap.peek()[1]){ minHeap.poll(); } minHeap.offer(interval); minRooms = Math.max(minHeap.size(), minRooms); } return minRooms;