Final: How Many Rooms?

Lab C++ Advanced 30 points

Print the fewest rooms needed for n meetings so overlapping meetings never share a room (a meeting can start right when another ends). Sort by start; keep a min-heap of end times.

Input

Line 1: n. Then n lines start end.

Output

One number.

Example

Input

Output

Sample input available Sample output available

Editor

C++

Hints

Sort meetings by start.

Pop every end time ≤ the new start, then push the new end.

The largest heap size is the answer.

Solution explanation

The heap holds meetings in progress; its size is the number of busy rooms.

Show solution

#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> m(n);
    for (auto& [s, e] : m) cin >> s >> e;
    sort(m.begin(), m.end());
    priority_queue<int, vector<int>, greater<int>> ends;
    size_t rooms = 0;
    for (auto [s, e] : m) {
        while (!ends.empty() && ends.top() <= s) ends.pop();
        ends.push(e);
        rooms = max(rooms, ends.size());
    }
    cout << rooms << endl;
    return 0;
}

Output

Answer