Meeting Rooms Problem Minimum Rooms Required in DSA Go

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 a single phone booth at different times. You want to know how many booths you need so that no one waits.

Meetings: [1,4], [2,5], [7,9]
Timeline: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
Rooms needed at times:
Time 1: Room 1 busy
Time 2: Room 1 and Room 2 busy
Time 7: Room 1 free, Room 2 free, Room 1 busy again

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 to track end times of ongoing meetings

Heap: []

Why: Heap helps us quickly find the earliest meeting that ends.

Step 3: Add first meeting end time 4 to heap

Heap: [4]

Why: First meeting occupies one room until time 4.

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

Heap: [4]

Why: 2 < 4 means overlap, need new room.

Step 5: Add second meeting end time 5 to heap

Heap: [4,5]

Why: Two meetings overlap, so two rooms needed.

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

Heap: [4,5]

Why: 7 >= 4 means first room is free now.

Step 7: Remove 4 from heap, add 9

Heap: [5,9]

Why: Reuse room freed at time 4 for meeting starting at 7.

Step 8: Check heap size for rooms needed

Heap size = 2

Why: Maximum rooms used at once is 2.

Result:

Heap: [5,9]
Minimum rooms required: 2

Annotated Code

DSA Go

package main

import (
	"container/heap"
	"fmt"
	"sort"
)

type Interval struct {
	start int
	end   int
}

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
	n := len(*h)
	x := (*h)[n-1]
	*h = (*h)[:n-1]
	return x
}

func minMeetingRooms(intervals []Interval) int {
	if len(intervals) == 0 {
		return 0
	}

	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i].start < intervals[j].start
	})

	endTimes := &MinHeap{}
	heap.Init(endTimes)

	heap.Push(endTimes, intervals[0].end) // add first meeting end time

	for i := 1; i < len(intervals); i++ {
		if intervals[i].start >= (*endTimes)[0] {
			heap.Pop(endTimes) // room freed, reuse it
		}
		heap.Push(endTimes, intervals[i].end) // add current meeting end time
	}

	return endTimes.Len() // number of rooms needed
}

func main() {
	meetings := []Interval{{1, 4}, {2, 5}, {7, 9}}
	rooms := minMeetingRooms(meetings)
	fmt.Printf("Minimum rooms required: %d\n", rooms)
}

sort.Slice(intervals, func(i, j int) bool { return intervals[i].start < intervals[j].start })

sort meetings by start time to process in order

heap.Push(endTimes, intervals[0].end) // add first meeting end time

add first meeting end time to track room usage

if intervals[i].start >= (*endTimes)[0] { heap.Pop(endTimes) }

if current meeting starts after earliest end, reuse room

heap.Push(endTimes, intervals[i].end)

add current meeting end time to heap

return endTimes.Len()

number of rooms needed equals heap size

Output

Minimum rooms required: 2

Complexity Analysis

Time: O(n log n) because we sort the meetings and then for each meeting we do heap operations which take O(log n)

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

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

Edge Cases

empty list of meetings

returns 0 rooms needed

DSA Go

if len(intervals) == 0 { return 0 }

all meetings non-overlapping

returns 1 room needed

DSA Go

if intervals[i].start >= (*endTimes)[0] { heap.Pop(endTimes) }

all meetings fully overlapping

returns number of meetings as rooms needed

DSA Go

heap.Push(endTimes, intervals[i].end)

When to Use This Pattern

When you see a problem asking for minimum number of rooms or resources to schedule overlapping intervals, use the min-heap approach to track earliest finishing meeting and reuse rooms.

Common Mistakes

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

Mistake: Not reusing rooms by checking earliest end time
Fix: Use a min-heap to track earliest end time and pop it when a room frees up

Summary

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

Use when scheduling overlapping intervals and you want to minimize resources.

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

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