Meeting Rooms Problem Minimum Rooms Required in DSA Go - Build from Scratch

Meeting Rooms Problem Minimum Rooms Required

📖 Scenario: You are organizing meetings in a conference center. Each meeting has a start time and an end time. You want to find out the minimum number of rooms needed so that all meetings can happen without overlapping in the same room.

🎯 Goal: Build a Go program that calculates the minimum number of meeting rooms required given a list of meeting time intervals.

📋 What You'll Learn

Create a slice of meeting intervals with exact start and end times

Create a slice to hold start times and a slice to hold end times

Implement the logic to find the minimum number of rooms needed

Print the minimum number of rooms required

💡 Why This Matters

🌍 Real World

This problem helps in scheduling meetings or events efficiently in limited rooms, avoiding conflicts.

💼 Career

Understanding interval scheduling and resource allocation is important for software engineers working on calendar apps, booking systems, and event management software.

1

Create the meeting intervals data

Create a slice of meeting intervals called meetings with these exact intervals: {Start: 0, End: 30}, {Start: 5, End: 10}, and {Start: 15, End: 20}. Define a struct type Interval with Start and End as integers.

DSA Go

type Interval struct {
    Start int
    End int
}

// Your code here

Hint

Define a struct named Interval with two integer fields: Start and End. Then create a slice named meetings with the given intervals.

2

Extract start and end times into separate slices

Create two slices of integers called starts and ends. Fill starts with the start times and ends with the end times from the meetings slice.

DSA Go

package main

import "fmt"

type Interval struct {
    Start int
    End int
}

func main() {
    meetings := []Interval{{Start: 0, End: 30}, {Start: 5, End: 10}, {Start: 15, End: 20}}
    // Your code here
}

Hint

Use a for loop to go through each meeting in meetings. Append the Start time to starts and the End time to ends.

3

Calculate the minimum number of meeting rooms

Sort the starts and ends slices. Use two pointers startPtr and endPtr to traverse these slices. Create variables rooms and maxRooms to track current and maximum rooms needed. Increase rooms when a meeting starts before another ends, otherwise decrease rooms. Update maxRooms accordingly.

DSA Go

package main

import "fmt"

import "sort"

type Interval struct {
    Start int
    End int
}

func main() {
    meetings := []Interval{{Start: 0, End: 30}, {Start: 5, End: 10}, {Start: 15, End: 20}}
    starts := []int{}
    ends := []int{}
    for _, meeting := range meetings {
        starts = append(starts, meeting.Start)
        ends = append(ends, meeting.End)
    }
    // Your code here
}

Hint

Sort both starts and ends. Use two pointers to compare start and end times. Increase rooms when a meeting starts before another ends, else decrease it. Keep track of the maximum rooms needed.

4

Print the minimum number of meeting rooms required

Print the value of maxRooms using fmt.Println.

DSA Go

package main

import "fmt"

import "sort"

type Interval struct {
    Start int
    End int
}

func main() {
    meetings := []Interval{{Start: 0, End: 30}, {Start: 5, End: 10}, {Start: 15, End: 20}}
    starts := []int{}
    ends := []int{}
    for _, meeting := range meetings {
        starts = append(starts, meeting.Start)
        ends = append(ends, meeting.End)
    }

    sort.Ints(starts)
    sort.Ints(ends)

    rooms := 0
    maxRooms := 0
    startPtr := 0
    endPtr := 0

    for startPtr  maxRooms {
                maxRooms = rooms
            }
            startPtr++
        } else {
            rooms--
            endPtr++
        }
    }
    // Your code here
}

Hint

Use fmt.Println(maxRooms) to print the minimum number of meeting rooms required.

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