Minimum Meeting Rooms: How Many Rooms Do You Really Need?

Minimum Meeting Rooms

Imagine you run an office. Many meetings are booked for the day. Each meeting has a start time and an end time. Two meetings can share the same room *only* if they do not happen at the same time. If two meetings overlap, each one needs its own room.

The question is simple: what is the smallest number of rooms you must have so that every meeting can take place? You don't want to waste money on extra rooms, but you also can't leave a meeting without a place to happen.

The input

You are given a list of meetings. Each meeting is a pair of two numbers:

[[s1, e1], [s2, e2], ...]

Here s is the start time and e is the end time. The problem promises that si < ei — a meeting always ends after it starts, which makes sense.

When do two meetings overlap?

This is the key rule, and it must be understood carefully.

Two meetings [s1, e1] and [s2, e2] overlap if:

e1 > s2

In plain words: the first meeting is still going on when the second one starts. They clash, so they cannot use the same room.

But there is an important edge case:

• If e1 == s2, they do not overlap. One meeting ends at the exact moment the next one begins. The room is free just in time, so the same room can be reused.

Think of it like checking out of a hotel room and the next guest checking in at the same minute — that is allowed.

Walking through the example

Input: meetings = [[1, 20], [10, 30], [30, 40], [1, 5]]
Output: 2

Let's see why 2 rooms are enough.

• The meeting [1, 5] and the meeting [1, 20] both start at time 1. They are happening at the same time, so we need two rooms here — one for each.
• The meeting [1, 5] ends at time 5. After that, its room becomes free. Later, the meeting [10, 30] can use that same room (since 10 is after 5, there is no clash).
• The meeting [30, 40] starts exactly when [10, 30] ends (30 == 30). By the rule, this is not an overlap, so the same room is reused again.

At no single moment are more than two meetings happening together. So 2 rooms are enough. That is the answer.

The big idea

The minimum number of rooms equals the largest number of meetings that are happening at the same moment. Find the busiest instant of the day — the number of meetings overlapping at that instant is exactly how many rooms you need.

The code skeleton

You will write your solution inside this function:

class Solution {
public:
    int minimumMeetingRooms(vector<vector<int>> meetings) {
        // your code here
    }
};

It takes the list of meetings and returns a single integer: the minimum number of rooms.