Meeting Rooms Problem Minimum Rooms Required in DSA C

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 few study rooms. Each friend has a start and end time. You want to know how many rooms you need so that no two friends share a room at the same time.

Meetings: [1,4], [2,5], [7,9]
Timeline: 1 2 3 4 5 6 7 8 9
Rooms needed:
Room1: [1,4]       [7,9]
Room2:    [2,5]

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 process meetings in order of when they start.

Step 2: Create a min-heap to track meeting end times, add first meeting end time 4

Heap: [4]

Why: We track earliest finishing meeting to reuse rooms.

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

Heap: [4,5]

Why: 2 < 4 means overlap, need new room, add end time 5.

Step 4: Check third meeting start 7 against earliest end 4 in heap

Heap after removing 4: [5]
Add 9: [5,9]

Why: 7 >= 4 means room freed, remove 4, add 9.

Result:

Heap size is 2, so minimum rooms needed = 2

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Structure for a meeting interval
typedef struct {
    int start;
    int end;
} Interval;

// Compare function for qsort to sort intervals by start time
int compare(const void *a, const void *b) {
    Interval *i1 = (Interval *)a;
    Interval *i2 = (Interval *)b;
    return i1->start - i2->start;
}

// Min-heap structure for end times
typedef struct {
    int *arr;
    int size;
    int capacity;
} MinHeap;

MinHeap* createHeap(int capacity) {
    MinHeap *heap = (MinHeap *)malloc(sizeof(MinHeap));
    heap->arr = (int *)malloc(sizeof(int) * capacity);
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapifyUp(MinHeap *heap, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap->arr[parent] <= heap->arr[index])
            break;
        swap(&heap->arr[parent], &heap->arr[index]);
        index = parent;
    }
}

void heapifyDown(MinHeap *heap, int index) {
    int left, right, smallest;
    while (1) {
        left = 2 * index + 1;
        right = 2 * index + 2;
        smallest = index;
        if (left < heap->size && heap->arr[left] < heap->arr[smallest])
            smallest = left;
        if (right < heap->size && heap->arr[right] < heap->arr[smallest])
            smallest = right;
        if (smallest == index)
            break;
        swap(&heap->arr[smallest], &heap->arr[index]);
        index = smallest;
    }
}

void insertHeap(MinHeap *heap, int val) {
    if (heap->size == heap->capacity) return; // no resize for simplicity
    heap->arr[heap->size] = val;
    heapifyUp(heap, heap->size);
    heap->size++;
}

int getMin(MinHeap *heap) {
    if (heap->size == 0) return -1;
    return heap->arr[0];
}

void removeMin(MinHeap *heap) {
    if (heap->size == 0) return;
    heap->arr[0] = heap->arr[heap->size - 1];
    heap->size--;
    heapifyDown(heap, 0);
}

int minMeetingRooms(Interval* intervals, int intervalsSize) {
    if (intervalsSize == 0) return 0;

    // Sort intervals by start time
    qsort(intervals, intervalsSize, sizeof(Interval), compare);

    // Create min heap for end times
    MinHeap *heap = createHeap(intervalsSize);

    // Add first meeting end time
    insertHeap(heap, intervals[0].end);

    for (int i = 1; i < intervalsSize; i++) {
        int earliestEnd = getMin(heap);
        if (intervals[i].start >= earliestEnd) {
            // Room freed, remove earliest end
            removeMin(heap);
        }
        // Add current meeting end time
        insertHeap(heap, intervals[i].end);
    }

    int rooms = heap->size;
    free(heap->arr);
    free(heap);
    return rooms;
}

int main() {
    Interval meetings[] = {{1,4}, {2,5}, {7,9}};
    int n = sizeof(meetings) / sizeof(meetings[0]);
    int result = minMeetingRooms(meetings, n);
    printf("Minimum rooms needed: %d\n", result);
    return 0;
}

qsort(intervals, intervalsSize, sizeof(Interval), compare);

Sort meetings by start time to process in order

insertHeap(heap, intervals[0].end);

Add first meeting end time to heap

int earliestEnd = getMin(heap);

Get earliest finishing meeting end time

if (intervals[i].start >= earliestEnd) { removeMin(heap); }

If current meeting starts after earliest end, reuse room by removing earliest end

insertHeap(heap, intervals[i].end);

Add current meeting end time to heap

Output

Minimum rooms needed: 2

Complexity Analysis

Time: O(n log n) because we sort the meetings and then insert/remove from a heap for each meeting

Space: O(n) for the heap that stores end times of ongoing meetings

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

Edge Cases

No meetings

Returns 0 rooms needed

DSA C

if (intervalsSize == 0) return 0;

All meetings non-overlapping

Returns 1 room needed

DSA C

if (intervals[i].start >= earliestEnd) { removeMin(heap); }

All meetings fully overlapping

Returns number of meetings as rooms needed

DSA C

insertHeap(heap, intervals[i].end);

When to Use This Pattern

When you need to find the minimum number of resources (rooms) 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 earliest ending meeting when room is freed
Fix: Remove earliest end from heap when current meeting can reuse that room

Summary

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

Use when scheduling intervals to minimize resource usage like rooms or machines.

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