Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Problem Challenge 1: Minimum Meeting Rooms (hard)

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!
anup kalia

anup kalia

· 2 years ago

class Solution:
  def findMinimumMeetingRooms(self, meetings):
    if not meetings:
        return 0

    # sort the meetings by start time
    meetings.sort(key=lambda x: x.start)

    minRooms = 0
    minHeap = []
    for meeting in meetings:
        # remove all meetings that have ended
        while minHeap and meeting.start >= minHeap[0]:
            heapq.heappop(minHeap)
        # add the current meeting into the minHeap
        heapq.heappush(minHeap, meeting.end)
        # all active meetings are in the minHeap, so we need rooms for all of them.
        minRooms = max(minRooms, len(minHeap))
    return minRooms
Show 1 reply
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;

A

Angel Morales

· 4 years ago

I did it using the sliding window technique we used previously

public static int findMinimumMeetingRooms(int[][] meetings) { Arrays.sort(meetings, Comparator.comparingInt(a -> a[0])); System.out.println(Arrays.deepToString(meetings)); int count = 1; int result= 1; int start = 0; for (int end = 1; end < meetings.length ; end++) { if (meetings[end][0] < meetings[end-1][1]){ count++; }else{ count =1; } while(count > 2 && meetings[start][1]

Nitin Varun

Nitin Varun

· 3 years ago

Please add the below case as well for Accepting the Solution.

[[1, 3], [2, 8], [4, 9], [5, 10], [6, 10]]
A

Azimul Haque

· 3 years ago

I am a beginner and want to understand if the (hard) and (medium) mentioned for each problem are comparable with how the 'hard' and 'medium' questions are labeled in leetcode.

Show 2 replies
V

Vansh Arora

· 3 years ago

Code will be similar to merge intervals, but instead of replacing currentInterval with merged interval, we will set currentInterval to intersection of current and nextInterval.Please see code below and let me know if there are any issues with this approach:

static int findMinimumMeetingRooms(vector<Meeting> &meetings) {
    sort(meetings.begin(), meetings.end(),
      [] (const Meeting &first, const Meeting &second) { return first.start < second.start; });
    
    int minRooms = 1, currentRooms = 1;
    Meeting currentMeeting = meetings[0];
    for (int next = 1; next < meetings.size(); next++) {
      // If there is an overlap
      if (meetings[next].start < currentMeeting.end) {
        currentRooms++;
        // Find intersection and set currentMeeting to the intersecti
Show 1 reply
H

hn200000

· 2 years ago

For some reason, the solution was altered. The solution is not correct anymore. it doesn’t have the min heap

Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

import heapq

#class Meeting:
#  def __init__(self, start, end):
#    self.start = start
#    self.end = end

# You can override/modify __lt__ as per your need
#setattr(Meeting, "__lt__", lambda self, other: write logic here)


class Solution:
  def findMinimumMeetingRooms(self, meetings):
    
    meetings.sort(key = lambda x: x.start)
    
    min_rooms = 1

    def do_overlap(a, b):
      return b.start < a.end

    overlap_found = False

    for i in range(1, len(meetings)):
      
      if overlap_found and not do_overlap(meetings[i - 1], meetings[i]):
         overlap_found = False

      # Count the overlap only once so we need the overlap_found for that   
      elif not overlap_found and do_overlap(meetings[i - 1], meetings[i]):
        min_rooms += 1
        overlap
Show 1 reply
bhairava s

bhairava s

· 2 years ago

Just check this : remove the interval in heap when current interval do not overlap (Non-overlap) with first interval in heap

Sachin Dev S

Sachin Dev S

· 2 years ago


  public int findMinimumMeetingRooms(List<Meeting> meetings) {
    int overlap = 0, maxOverlap = 0, n = meetings.size();
    if(n==0) return 0;
    meetings.sort((a,b)->Integer.compare(a.start,b.start));

    Meeting curr = meetings.get(0);
    int start = curr.start, end = curr.end;
    for(int i = 1; i < n; i++) {
      curr = meetings.get(i);
      if(end > curr.start) {
        overlap++;
        maxOverlap = Math.max(maxOverlap, overlap);
      }

      if(curr.end > end) {
        overlap = 0;
        start = curr.start;
        end = curr.end;
      }
    }

    return maxOverlap + 1;
  }