n meetings want one room; each has a start and an end time. What is the largest number that can use the room without overlapping? A meeting may start exactly when another ends.
Input
The first line has n (1 ≤ n ≤ 1000). Each of the next n lines has a start and an end (0 ≤ start < end ≤ 10⁹), in any order.
Output
The largest number of meetings.
Examples
Example 1 · Input
6 1 4 3 5 0 6 5 7 8 9 5 9
Expected output
3
Example 2 · Input
3 1 10 2 3 4 5
Expected output
2
Hints
Hint 1
Store the meetings as pair<int, int> and sort them by end time with a comparison function.
Hint 2
Take a meeting if it starts at or after the end of the last one taken.
Solution
Show one correct solution (try it yourself first)
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
bool byEnd(const pair<int, int>& a, const pair<int, int>& b) {
return a.second < b.second;
}
int main() {
int n;
cin >> n;
vector<pair<int, int>> m(n);
for (auto& p : m) cin >> p.first >> p.second;
sort(m.begin(), m.end(), byEnd);
int count = 0, lastEnd = -1;
for (auto& p : m) {
if (p.first >= lastEnd) {
count++;
lastEnd = p.second;
}
}
cout << count << "\n";
return 0;
}