Meeting Rooms Problem Minimum Rooms Required in DSA Go - Execution Trace

Concept Flow - Meeting Rooms Problem Minimum Rooms Required

Sort intervals by start time

↓

Initialize min-heap for end times

↓

For each interval

↓

If min-heap top <= interval start

↓

Pop from min-heap

↓

Push current interval end

↓

Else push current interval end

↓

Heap size = minimum rooms needed

Sort meetings by start time, use a min-heap to track earliest ending meeting, reuse rooms if possible, heap size shows minimum rooms.

Execution Sample

DSA Go

intervals := [][]int{{0,30},{5,10},{15,20}}
sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
minHeap := &IntHeap{}
heap.Init(minHeap)
for _, interval := range intervals {
  if minHeap.Len() > 0 && (*minHeap)[0] <= interval[0] {
    heap.Pop(minHeap)
  }
  heap.Push(minHeap, interval[1])
}
return minHeap.Len()

This code finds the minimum number of meeting rooms needed by sorting intervals and using a min-heap to track room availability.

Execution Table

Step	Operation	Current Interval	Min-Heap Before	Heap Action	Min-Heap After	Rooms Needed	Visual State
1	Sort intervals	[0,30]	[]	N/A	[]	0	[]
2	Process interval	[0,30]	[]	Push 30	[30]	1	[0,30]
3	Process interval	[5,10]	[30]	Push 10	[10,30]	2	[0,30] -> [5,10]
4	Process interval	[15,20]	[10,30]	Pop 10, Push 20	[20,30]	2	[0,30] -> [15,20]
5	End	N/A	[20,30]	N/A	[20,30]	2	Final rooms: 2

💡 All intervals processed; min-heap size 2 means minimum 2 rooms needed.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
intervals	[[0,30],[5,10],[15,20]]	[[0,30],[5,10],[15,20]]	[[0,30],[5,10],[15,20]]	[[0,30],[5,10],[15,20]]	[[0,30],[5,10],[15,20]]
minHeap	[]	[30]	[10,30]	[20,30]	[20,30]
roomsNeeded	0	1	2	2	2

Key Moments - 3 Insights

Why do we pop from the min-heap when the earliest end time is less or equal to the current start?

Because the room with the earliest finishing meeting is now free and can be reused for the current meeting, reducing the total rooms needed. See step 4 in execution_table where 10 is popped before pushing 20.

Why do we push the current interval's end time into the min-heap every time?

We always push the current meeting's end time to track when that room will be free. This keeps the min-heap updated with all ongoing meetings' end times. See steps 2, 3, and 4 in execution_table.

Why does the size of the min-heap represent the minimum number of rooms needed?

Because each end time in the min-heap represents a meeting currently occupying a room. The heap size shows how many rooms are in use simultaneously. At the end, this is the minimum rooms required. See final step in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the min-heap state before processing the interval [5,10]?

A []

B [30]

C [10,30]

D [20,30]

💡 Hint

Check the 'Min-Heap Before' column at step 3 in execution_table.

At which step does the min-heap size first become 2?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Rooms Needed' column in execution_table for each step.

If the interval [5,10] was changed to [35,40], how would the min-heap size after step 3 change?

A It would remain 1

B It would become 2

C It would become 3

D It would become 0

💡 Hint

Consider if the earliest end time in min-heap is <= new interval start, allowing reuse.

Concept Snapshot

Meeting Rooms Minimum Rooms Required:
- Sort intervals by start time
- Use min-heap to track earliest end time
- For each interval:
  - If earliest end <= current start, pop heap
  - Push current end
- Heap size = minimum rooms needed

Full Transcript

To find the minimum number of meeting rooms needed, first sort all meeting intervals by their start times. Then, use a min-heap to keep track of the end times of meetings currently occupying rooms. For each meeting, check if the earliest finishing meeting ends before or when the current meeting starts. If yes, that room can be reused, so pop the earliest end time from the heap. Then push the current meeting's end time into the heap. The size of the heap after processing all meetings shows the minimum number of rooms required. This approach efficiently manages room allocation by reusing rooms whenever possible.

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 earliest meeting start time

B. The maximum length of a single meeting

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

D. The total number of meetings scheduled

Solution

1. Step 1: Understand the problem goal

   The problem asks for the minimum number of rooms needed 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 required.

3. Final Answer:

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

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 Go data structure is best to store meeting intervals for solving the minimum rooms problem?

easy

A. [][]int

B. string

C. map[int]int

D. chan int

Solution

1. Step 1: Identify suitable data structure for intervals

   Meeting intervals have start and end times, so a slice of slices ([][]int) is ideal to store pairs.

2. Step 2: Check other options

   map[int]int is less natural for intervals, string can't hold numeric ranges, chan int is for concurrency, not intervals.

3. Final Answer:

   [][]int -> Option A

4. Quick Check:

   Intervals stored as pairs in [][]int [OK]

Hint: Use [][]int to hold start and end times pairs [OK]

Common Mistakes:

• Using map which doesn't keep order
• Trying to store intervals as strings
• Using channels which are unrelated here

3. What is the output of the following Go code snippet that calculates minimum meeting rooms needed?

intervals := [][]int{{0, 30}, {5, 10}, {15, 20}}
rooms := minMeetingRooms(intervals)
fmt.Println(rooms)

func minMeetingRooms(intervals [][]int) int {
    starts := []int{}
    ends := []int{}
    for _, interval := range intervals {
        starts = append(starts, interval[0])
        ends = append(ends, interval[1])
    }
    sort.Ints(starts)
    sort.Ints(ends)
    rooms, endIndex := 0, 0
    for i := 0; i < len(starts); i++ {
        if starts[i] < ends[endIndex] {
            rooms++
        } else {
            endIndex++
        }
    }
    return rooms
}

medium

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Sort start and end times

   Starts = [0,5,15], Ends = [10,20,30]

2. Step 2: Iterate and count rooms

   At start=0 < end=10, rooms=1; start=5 < end=10, rooms=2; start=15 >= end=10, endIndex++, rooms=2

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Max overlapping meetings = 2 [OK]

Hint: Sort starts and ends, count overlaps to find rooms [OK]

Common Mistakes:

• Not sorting start and end times
• Incrementing rooms incorrectly
• Confusing start and end comparisons

4. Find the bug in this Go function for minimum meeting rooms:

func minMeetingRooms(intervals [][]int) int {
    starts := []int{}
    ends := []int{}
    for _, interval := range intervals {
        starts = append(starts, interval[0])
        ends = append(ends, interval[1])
    }
    sort.Ints(starts)
    sort.Ints(ends)
    rooms := 0
    endIndex := 0
    for i := 0; i <= len(starts); i++ {
        if starts[i] < ends[endIndex] {
            rooms++
        } else {
            endIndex++
        }
    }
    return rooms
}

medium

A. Loop condition should be i < len(starts), not <= to avoid out-of-range

B. Should sort starts and ends in descending order

C. Should compare starts[i] > ends[endIndex] instead

D. Should initialize rooms to 1 instead of 0

Solution

1. Step 1: Check loop boundary

   The loop uses i <= len(starts), which causes index out-of-range error because valid indices are 0 to len(starts)-1.

2. Step 2: Correct loop condition

   Change to i < len(starts) to safely iterate over all elements.

3. Final Answer:

   Loop condition should be i < len(starts), not <= to avoid out-of-range -> Option A

4. Quick Check:

   Index error fixed by proper loop bounds [OK]

Hint: Use < not <= in loops to avoid index errors [OK]

Common Mistakes:

• Using <= instead of < in for loops
• Sorting in wrong order
• Wrong comparison operators

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

hard

A. 3

B. 1

C. 4

D. 2

Solution

1. Step 1: Sort start and end times

   Starts = [1,2,6,7,9], Ends = [4,5,8,9,10]

2. Step 2: Count overlaps to find rooms

   i=0 start=1 < end=4 rooms=1 i=1 start=2 < end=4 rooms=2 i=2 start=6 >= end=4 endIndex=1 rooms=2 i=3 start=7 >= end=5 endIndex=2 rooms=2 i=4 start=9 >= end=8 endIndex=3 rooms=2

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Max overlaps = 2 rooms needed [OK]

Hint: Sort starts and ends, increment rooms on overlap [OK]

Common Mistakes:

• Not sorting intervals before processing
• Miscounting overlaps at boundaries
• Assuming one room per meeting always