Minimum Platforms / Meeting Rooms — Resource Allocation

Key Insight

Create arrival and departure events. Sort all events by time. Sweep through: arrivals need a platform (+1), departures free one (-1). The peak concurrent count is the answer.

Algorithm

events = merge(arrivals as +1, departures as -1)
sort events by time
platforms = 0, maxPlatforms = 0
for each event:
platforms += event.type
maxPlatforms = max(maxPlatforms, platforms)

Interactive Visualization

Arrival (+1)

Departure (-1)

Peak

Sorted Events

Active Platforms

Step 0 of 0

Current

Peak (Answer)

Arrivals

Departures

Ready. Press Play or Next to start.

✓ Done

Speed

C++ — Minimum Platforms

int minPlatforms(vector<int>& arr, vector<int>& dep) {
    sort(arr.begin(), arr.end());
    sort(dep.begin(), dep.end());

    int plat = 0, maxPlat = 0;
    int i = 0, j = 0, n = arr.size();

    while (i < n && j < n) {
        if (arr[i] <= dep[j]) {
            plat++; i++;          // arrival
            maxPlat = max(maxPlat, plat);
        } else {
            plat--; j++;          // departure
        }
    }
    return maxPlat;
}

Complexity

Time

O(N log N)

Sorting two arrays.

Space

O(1)

Two pointer sweep.

📝 Notes

▼