Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Problem Challenge 1: Minimum Meeting Rooms

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

public int findMinimumMeetingRooms(List<Meeting> meetings) {
    int n = meetings.size();
    int[] starr = new int[n], endarr = new int[n];
    for(int i = 0; i < n; i++) {
      starr[i] = meetings.get(i).start;
      endarr[i] = meetings.get(i).end;
    }

    Arrays.sort(starr);
    Arrays.sort(endarr);

    int  i = 0, j = 0, count = 0, max = 0;
    while(i < n && j < n) {
      if(starr[i] < endarr[j]) { // meeting started
        count++;
        i++;
      } else { // meeting ends
        count--;
        j++;
      }
      max = Math.max(count, max); // max no of rooms occupied right now
    }

    return max;
  }
A

Anonymous

· 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;
  }
A

Anonymous

· 2 years ago

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

A

Anonymous

· 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
A

Anonymous

· 3 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
A

Anonymous

· 3 years ago

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

A

Anonymous

· 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

Anonymous

· 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
A

Anonymous

· 4 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
A

Anonymous

· 4 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;

Reading Progress

0%

Vote for new content