Meeting Rooms Problem Minimum Rooms Required in DSA Javascript

Mental Model

We want to find the smallest number of rooms needed so that no meetings overlap in the same room.

Analogy: Imagine you have several friends who want to use the same study room at different times. You want to know how many rooms you need so everyone can study without waiting.

Meetings: [1,4], [2,5], [7,9]
Timeline: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
Rooms needed: 2 at time 2-4, 1 at time 7-9

Dry Run Walkthrough

Input: meetings: [[1,4], [2,5], [7,9]]

Goal: Find the minimum number of rooms needed so no meetings overlap in the same room.

Step 1: Sort meetings by start time

[[1,4], [2,5], [7,9]]

Why: Sorting helps us check meetings in order of when they start.

Step 2: Create a min-heap for end times and add first meeting end time 4

Heap: [4]

Why: We track when rooms get free by storing meeting end times.

Step 3: Check second meeting start 2 against earliest end time 4

2 < 4 means overlap, add end time 5 to heap

Why: Since meeting 2 starts before room 1 is free, we need a new room.

Step 4: Check third meeting start 7 against earliest end time 4

7 >= 4 means room freed, remove 4 from heap and add 9

Why: Room with meeting ending at 4 is free, reuse it for meeting starting at 7.

Result:

Heap size is 2, so minimum rooms needed = 2

Annotated Code

DSA Javascript

class MinHeap {
  constructor() {
    this.heap = []
  }
  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]
  }
  push(val) {
    this.heap.push(val)
    this.bubbleUp()
  }
  bubbleUp() {
    let index = this.heap.length - 1
    while (index > 0) {
      let parent = Math.floor((index - 1) / 2)
      if (this.heap[parent] <= this.heap[index]) break
      this.swap(parent, index)
      index = parent
    }
  }
  pop() {
    if (this.heap.length === 1) return this.heap.pop()
    const top = this.heap[0]
    this.heap[0] = this.heap.pop()
    this.bubbleDown()
    return top
  }
  bubbleDown() {
    let index = 0
    const length = this.heap.length
    while (true) {
      let left = 2 * index + 1
      let right = 2 * index + 2
      let smallest = index
      if (left < length && this.heap[left] < this.heap[smallest]) smallest = left
      if (right < length && this.heap[right] < this.heap[smallest]) smallest = right
      if (smallest === index) break
      this.swap(index, smallest)
      index = smallest
    }
  }
  peek() {
    return this.heap[0]
  }
  size() {
    return this.heap.length
  }
}

function minMeetingRooms(intervals) {
  if (intervals.length === 0) return 0
  intervals.sort((a, b) => a[0] - b[0])
  const heap = new MinHeap()
  heap.push(intervals[0][1])
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] >= heap.peek()) {
      heap.pop() // room freed
    }
    heap.push(intervals[i][1])
  }
  return heap.size()
}

// Driver code
const meetings = [[1,4], [2,5], [7,9]]
console.log(minMeetingRooms(meetings))

intervals.sort((a, b) => a[0] - b[0])

Sort meetings by start time to process in order

heap.push(intervals[0][1])

Add first meeting end time to heap to track room usage

if (intervals[i][0] >= heap.peek()) { heap.pop() }

If current meeting starts after earliest room frees, reuse that room

heap.push(intervals[i][1])

Add current meeting end time to heap to mark room occupied

return heap.size()

Number of rooms needed equals heap size at end

Output

2

Complexity Analysis

Time: O(n log n) because we sort the meetings and use a heap to track room end times

Space: O(n) because in worst case all meetings overlap and heap stores all end times

vs Alternative: A naive approach checks all pairs for overlap O(n^2), this heap method is more efficient

Edge Cases

empty meetings list

returns 0 rooms needed

DSA Javascript

if (intervals.length === 0) return 0

all meetings non-overlapping

returns 1 room needed

DSA Javascript

if (intervals[i][0] >= heap.peek()) { heap.pop() }

all meetings fully overlapping

returns number of meetings as rooms needed

DSA Javascript

heap.push(intervals[i][1])

When to Use This Pattern

When you see a problem asking for minimum number of rooms or resources to schedule overlapping intervals, use a min-heap to track earliest finishing times and allocate rooms efficiently.

Common Mistakes

Mistake: Not sorting meetings by start time before processing
Fix: Sort intervals by start time first to process in chronological order

Mistake: Not removing freed rooms from heap before adding new meeting
Fix: Check if current meeting can reuse a room by comparing start time with earliest end time and pop from heap if possible

Summary

Finds the minimum number of rooms needed so no meetings overlap in the same room.

Use when scheduling multiple intervals and you want to minimize resource usage.

Sort meetings by start time and use a min-heap to track earliest finishing meeting to reuse rooms.

Practice

1. What does the "Meeting Rooms Problem Minimum Rooms Required" ask you to find given a list of meeting time intervals?

easy

A. The minimum number of meeting rooms needed so no meetings overlap

B. The maximum length of a single meeting

C. The total number of meetings scheduled

D. The earliest meeting start time

Solution

1. Step 1: Understand the problem goal

   The problem asks for the minimum number of rooms required so that no two meetings overlap in the same room.

2. Step 2: Clarify what is being counted

   We count how many meetings happen at the same time to find the minimum rooms needed.

3. Final Answer:

   The minimum number of meeting rooms needed so no meetings overlap -> Option A

4. Quick Check:

   Minimum rooms = max overlapping meetings [OK]

Hint: Count max overlapping intervals to find rooms needed [OK]

Common Mistakes:

• Confusing total meetings with rooms needed
• Ignoring overlapping times
• Thinking earliest start time is the answer

2. Which of the following JavaScript code snippets correctly sorts an array of meeting intervals by their start time? Assume intervals is an array of objects with 'start' and 'end' properties.

easy

A. intervals.sort((a, b) => b.end - a.end);

B. intervals.sort((a, b) => b.start - a.start);

C. intervals.sort((a, b) => a.end - b.end);

D. intervals.sort((a, b) => a.start - b.start);

Solution

1. Step 1: Identify sorting by start time

   We want to sort intervals by their start property in ascending order.

2. Step 2: Check the sort function

   The comparator (a, b) => a.start - b.start sorts ascending by start time.

3. Final Answer:

   intervals.sort((a, b) => a.start - b.start); -> Option D

4. Quick Check:

   Ascending start time sort = intervals.sort((a, b) => a.start - b.start); [OK]

Hint: Sort intervals by start ascending: (a,b) => a.start - b.start [OK]

Common Mistakes:

• Sorting by end time instead of start
• Sorting descending when ascending needed
• Using incorrect comparator syntax

3. What is the minimum number of meeting rooms required for the following intervals?
const intervals = [{start: 0, end: 30}, {start: 5, end: 10}, {start: 15, end: 20}];

medium

A. 1

B. 2

C. 3

D. 4

Solution

1. Step 1: Analyze overlapping intervals

   Meetings: [0-30], [5-10], [15-20]. The first overlaps with the second and third.

2. Step 2: Count max overlaps

   At time 5-10, two meetings overlap (0-30 and 5-10). At 15-20, two meetings overlap (0-30 and 15-20). Max overlap is 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Max overlapping meetings = 2 rooms needed [OK]

Hint: Find max overlaps by checking intervals start and end times [OK]

Common Mistakes:

• Counting total meetings instead of overlaps
• Assuming 3 rooms because 3 meetings exist
• Ignoring overlap intervals

4. The following code attempts to find the minimum number of meeting rooms needed but has a bug. What is the bug?

function minMeetingRooms(intervals) {
  intervals.sort((a, b) => a.start - b.start);
  let rooms = [];
  for (let meeting of intervals) {
    if (rooms.length === 0 || meeting.start < rooms[rooms.length - 1]) {
      rooms.push(meeting.end);
    } else {
      rooms[rooms.length - 1] = meeting.end;
    }
  }
  return rooms.length;
}

medium

A. It returns the wrong value (should return rooms array)

B. It sorts intervals by end time instead of start time

C. It compares meeting.start with a number incorrectly (rooms array stores end times, but comparison is wrong)

D. It uses push instead of unshift on rooms array

Solution

1. Step 1: Understand rooms array usage

   Rooms array stores end times of meetings currently occupying rooms.

2. Step 2: Check comparison logic

   Comparing meeting.start with rooms[rooms.length - 1] (last end time) is incorrect because rooms should be a min-heap or sorted structure, not just last element.

3. Final Answer:

   It compares meeting.start with a number incorrectly (rooms array stores end times, but comparison is wrong) -> Option C

4. Quick Check:

   Incorrect comparison of start with last end time causes bug [OK]

Hint: Use a min-heap or sorted structure for end times, not last element [OK]

Common Mistakes:

• Comparing start with last end time without sorting
• Not using a priority queue for room end times
• Returning wrong variable

5. Given the intervals [[1,4],[2,5],[7,9],[6,10],[8,11]], what is the minimum number of meeting rooms required? Explain your reasoning.

hard

A. 3

B. 2

C. 4

D. 5

Solution

1. Step 1: Sort intervals by start time

   Sorted intervals: [1,4], [2,5], [6,10], [7,9], [8,11]

2. Step 2: Track overlapping meetings

   Between 1-5, two meetings overlap ([1,4] and [2,5]). Between 6-11, three meetings overlap ([6,10], [7,9], [8,11]). Max overlap is 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Max overlapping meetings = 3 rooms needed [OK]

Hint: Find max overlaps by checking intervals start and end times carefully [OK]

Common Mistakes:

• Not sorting intervals before checking overlaps
• Counting total meetings instead of max overlaps
• Missing overlaps in later intervals