예제가 힌트였다.
회의의 길이나 회의의 시작 시각 순으로 정렬해 시도했으나 정답을 얻지는 못했다.
회의가 끝나는 시각을 정렬해 일찍 끝나는 회의부터 추가했더니 풀 수 있었다.
현재까지 회의가 끝난 시각을 변수로 저장해두고, sort된 벡터의 원소를 하나씩 보면서 회의의 시작 시각이 가장 최근 회의의 종료 시각 이상일 경우 (==회의가 겹치지 않을 때) 회의의 종료 시각을 업데이트하고 cnt값을 증가시킨다.
구현
#include <iostream>
#include <vector>
#include <algorithm> // sort
using namespace std;
bool comparator (pair<int, int> p1, pair<int, int> p2) {
if (p1.second == p2.second) return p1.first < p2.first;
else return p1.second < p2.second;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
vector<pair <int, int> > v; // {start, end}
int N, cnt, now, start, end, i; // cnt: 회의의 개수; now: 방금 추가된 회의의 종료 시각
cin >> N;
for (i = 0; i < N; i++) {
cin >> start >> end;
v.push_back(make_pair(start, end));
}
sort(v.begin(), v.end(), comparator); // end (회의가 끝나는 시각)이 빠른 순서대로 회의를 정렬
cnt = 0;
now = 0;
for (auto it = v.begin(); it < v.end(); it++) {
pair<int, int> cur = *it;
start = cur.first;
end = cur.second;
if (start >= now) {
now = end;
cnt++;
}
}
cout << cnt << endl;
return 0;
}