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!

Dante Tsang

· 5 months ago

JS version without the heap (O(n² log n))


/*class Meeting {
  constructor(start, end) {
    this.start = start;
    this.end = end;
  }
}*/

class Solution {

  findMinimumMeetingRooms(meetings) {
    let minRooms = 0;
    // TODO: Write your code here
    meetings = meetings.sort((a, b) => a.start - b.start)

    let heap = [meetings[0].end]

    for (let i = 1; i < meetings.length; i++) {
      const earlistMeetiong = heap[0]
      const curr = meetings[i]

      if (earlistMeetiong <= curr.start) {
        heap.shift()
      }

      heap.push(curr.end)
      heap = heap.sort((a, b) => a - b)

    }


    return heap.length;
  }
}

Show 1 reply

michaeljroytman

· 8 months ago

Why do we need a heap? Am I missing something?

If we sort the meetings by start time (and end time if the start times are the same), then we can simply use sliding window to find the longest length of overlapping meetings.

When the meetings do not overlap, we move the left pointer. When they do, we move the right.

Runtime complexity is O(n logn) because of sorting.

Space complexity is O(1).


/*class Meeting {
  constructor(start, end) {
    this.start = start;
    this.end = end;
  }
}*/

class Solution {
  findMinimumMeetingRooms(meetings) {
    let minRooms = 0;
    /**
     * Sort the meetings by start time.
     * Then, apply sliding window.
     * 
     * When the meetings overlap, grow the window. when they do not, shrink it.
     * 
     * The maximum length o

Show 2 replies

Saahil Chaddha

· a year ago

Show 1 reply

Глеб Чистяков

· a year ago

class Solution {

  findMinimumMeetingRooms(meetings) {
    let minRooms = 1;
    let localRooms = 1

    meetings.sort((a, b) => a.start - b.start)
    
    let overlupEnd = meetings[0].end

    for (let index = 1; index < meetings.length; index++) {
      const interval = meetings[index]

      if (overlupEnd > interval.start) {
        overlupEnd = Math.min(interval.end, overlupEnd)
        localRooms += 1
        minRooms = Math.max(minRooms, localRooms)
      }
      else {
        minRooms = Math.max(minRooms, localRooms)
        localRooms = 1
        overlupEnd = interval.end
      }
    }

    return minRooms;
  }
}

Show 1 reply

Em Eff

· a year ago

With what looks like possible non-heap solutions posted, I'm not sure why the official solution uses one.

Here's a solution that leverages a Queue (or an array for simplicity's sake.) It basically just removes all meetings that start before the current then, after adding the current meeting to the queue, counts the max number rooms in use at any given time.

class Solution {
  findMinimumMeetingRooms(meetings) {
    let minRooms = 0

    meetings = meetings.sort((a, b) => a.start - b.start)

    const queue = []

    for(let meeting of meetings) {
      while(queue.length && queue[0].end <= meeting.start) {
        queue.shift()
      }

      queue.push(meeting)
      minRooms = Math.max(minRooms, queue.length)
    }

    return minRooms
  }
}

Show 1 reply

Debasis B

· 2 years ago

public class Solution
{
    /// <summary>
    /// O(n * log n)
    /// </summary>
    /// <param name="meetings"></param>
    /// <returns></returns>
    public int findMinimumMeetingRooms(List<Meeting> meetings)
    {
        meetings.Sort((x, y) => x.Start.CompareTo(y.Start));
        int rooms = 1;
        Meeting inProgress = meetings[0];
        for (int i = 1; i < meetings.Count; i++)
        {
            Meeting meeting = meetings[i];
            if (DoesIntersect(meeting, inProgress))
            {
                inProgress = FindIntersection(meeting, inProgress);
                rooms++;
            }
            else
            {
                inProgress = meeting;
            }
        }
        return rooms;
    }

    private bool DoesIntersect(Meeting meeting1,

Show 1 reply

Sachin Dev S

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

Show 1 reply

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

Show 1 reply

bhairava s

· 2 years ago

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

Reading Progress

Vote for new content