Challenge: Most Talks in One Room

Lab C++ Beginner 10 points

Print the largest number of non-overlapping talks that fit in one room (a talk may start exactly when another ends). Use the greedy “earliest end first” rule.

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 by end time.

Take a talk if it starts at or after the room is free.

Solution explanation

Finishing early always leaves the most room for the rest.

Show solution

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

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> t(n);
    for (auto& [s, e] : t) cin >> s >> e;
    sort(t.begin(), t.end(), [](const pair<int, int>& a, const pair<int, int>& b) { return a.second < b.second; });
    int count = 0, freeAt = -1;
    for (auto [s, e] : t)
        if (s >= freeAt) { count++; freeAt = e; }
    cout << count << endl;
    return 0;
}

Output

Answer