Minimum Number of Meeting Rooms

Meeting-room allocation must schedule every meeting and minimize the number of reusable rooms. Unlike activity selection, rejecting overlaps is not allowed. Processing meetings by start time and reusing any room whose last meeting has ended is optimal. Two min-heaps make the distinction between ongoing meetings and available room IDs explicit and allow the program to print a valid minimum-room assignment.

Prerequisites: Activity Selection; Priority Queues; interval endpoints. Related existing lessons: Priority Queues and Binary Heaps.

Build the idea

1. Model half-open meetings

   Each positive-duration meeting occupies [start,end), so a room is reusable at exactly end. Sort by start, then original ID. occupied stores (end,room) for ongoing meetings, and freeRooms stores released room IDs. room[id] restores assignments in input order. created counts all rooms ever allocated, not just rooms occupied right now.

2. Release before assigning

   Before a meeting starts, pop every occupied entry with end≤start and put its room ID in freeRooms. If a free room exists, reuse the smallest ID for deterministic output. Otherwise create a new ID. Push the assigned room with this meeting’s end. The heap key is finish time, so all completed rooms can be released without scanning every room.

   $$\mathrm{minimumRooms}=\mathrm{maximumSimultaneousMeetings}$$

3. Correctness proof: a matching lower bound

   When a new room is created, every previously created room is occupied at the new meeting’s start. Those ongoing meetings plus the new one overlap at that instant, so any schedule needs at least created rooms. Reusing free rooms never creates overlap within a room. Each increase therefore matches a necessary overlap lower bound, proving the final number optimal.

4. Trace the assignment

   For meetings (1,4),(2,3),(3,5),(5,6), assign room 1 to the first and room 2 to the second. At time 3 room 2 is released and used by the third. At time 5 both prior rooms are free, so use room 1 for the fourth. Assignments are [1,2,2,1], and the peak simultaneous occupancy is two.

   Meeting	Start	Released rooms	Assigned
   1	1	none	1
   2	2	none	2
   3	3	2	2
   4	5	1,2	1

5. Interpret related heap variants

   A heap storing one latest end per allocated room can also solve this problem, but its size counts allocated rooms rather than only currently occupied ones. This program avoids that ambiguity with a separate free-ID heap. If meetings have setup/cleanup delays, adjust the release time consistently; if intervals are closed, the equality condition changes. Those are modeling changes, not harmless implementation details.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<functional>
#include<utility>
struct Meeting{
    long long start,end;
    int id;
};
int main(){
    int n;
    std::cin>>n;
    std::vector<Meeting>a(n);
    for(int i=0;i<n;++i){
        std::cin>>a[i].start>>a[i].end;
        a[i].id=i;
    }
    std::sort(a.begin(),a.end(),[](Meeting x,Meeting y){
        return x.start!=y.start?x.start<y.start:x.id<y.id;
    });
    std::priority_queue<std::pair<long long,int>,std::vector<std::pair<long long,int>>,
        std::greater<std::pair<long long,int>>>
        occupied;
    std::priority_queue<int,std::vector<int>,std::greater<int>>freeRooms;
    std::vector<int>room(n);
    int created=0;
    for(Meeting m:a){
        while(!occupied.empty()&&occupied.top().first<=m.start){
            freeRooms.push(occupied.top().second);
            occupied.pop();
        }
        int id;
        if(freeRooms.empty()){
            id=++created;
        }
        else{
            id=freeRooms.top();
            freeRooms.pop();
        }
        room[m.id]=id;
        occupied.push({m.end,id}); // The occupied heap contains only ongoing meetings.
    }
    std::cout<<created<<'\n';
    for(int i=0;i<n;++i){
        std::cout<<room[i]<<(i+1==n?'\n':' ');
    }
    if(n==0){
        std::cout<<'\n';
    }
}

Complexity analysis

O(n log n) sort and O(n log n) total heap processing. Every meeting enters/leaves occupied once; room IDs may move through the free heap. O(n) meetings, assignments and heap storage.

Example input and output

Read n (0..100000), then meetings with −10^9≤start<end≤10^9. Print minimum room count, then room IDs in original input order. End/start equality permits reuse.

Input

4
1 4
2 3
3 5
5 6

Output

2
1 2 2 1

Room 2 is reused at time 3, and room 1 is reused at time 5. At time 2 both rooms are necessary.

Practical applications

Use for machines, classrooms and simultaneous resource capacity with fixed intervals. A sweep over starts/ends computes just the minimum count; the heap additionally reconstructs assignments. Activity selection instead discards meetings to keep one room.

Check your understanding

Why is creating a room unavoidable when freeRooms is empty?

Put it into practice

Check that no two overlapping meetings share a room in the output.