문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.
풀이
한 회의가 끝난 뒤 곧바로 다음 회의를 시작할 수 있으므로, 끝나는 시간이 빠른 회의부터 선택하는 그리디가 정답이다. 빨리 끝나는 회의를 먼저 잡아야 이후에 더 많은 회의를 남겨 둘 수 있다.
코드에서는 회의를 종료 시간 기준으로 정렬하고, 현재 선택한 회의의 끝나는 시간 이후에 시작할 수 있는 회의만 채택하면서 개수를 센다.
길이가 짧은 회의가 아니라 가장 빨리 끝나는 회의를 고르는 것이 핵심이다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Time {
public:
int start;
int end;
};
int N;
bool compare(Time t1, Time t2) {
if (t1.end == t2.end) {
return t1.start < t2.start;
}
else {
return t1.end < t2.end;
}
}
int solve(vector<Time> vec) {
int answer = 0, next = 0;
for (int i = 0; i < N; i++) {
if (vec[i].start >= next) {
next = vec[i].end;
answer++;
}
}
return answer;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
vector<Time> vec(N);
for (int i = 0; i < N; i++)
cin >> vec[i].start >> vec[i].end;
sort(vec.begin(), vec.end(), compare);
int answer = solve(vec);
cout << answer << '\n';
return 0;
}복잡도
- 시간 복잡도:
- 공간 복잡도: 정렬 기준
마무리
회의를 많이 넣으려면 길이보다 종료 시각을 봐야 한다. 끝나는 시간이 빠른 회의를 고르는 그리디가 전체 최적해로 이어진다.
