링크
https://www.acmicpc.net/problem/1931
문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.
풀이
이 문제는 어떻게 하면 최대 개수를 만들 수 있는지가 중요하다.
기준은 회의 시작시간, 회의 끝나는시간 두가지 방법으로 잡을 수 있다.
나는 회의 시작시간이 정렬하기 더 편하기에 이를 기준으로 잡았다.
일단 설명하기 앞서 시작시간을 기준으로 오름차순 정렬하였다고 가정하겠다.
가장 끝 인덱스부터 검사를 시작하는데 시작시간이 겹치더라도 끝시간이 어떻게 분포되어있던 무조건 같은 시작시간을 가졌다면 하나밖에 들어갈 수 없다.
예를 들어, 8시가 가장 마지막에 시작하는 회의시간이라고 할 때, (8, 10), (8, 11), (8, 13)의 회의가 있다면 셋 중 아무거나 들어가도 무방하다. 8시 이후에 시작하는 회의가 없기 때문이다.
한가지 생각해야할 것은 시작시간과 끝시간이 같은 회의이다. 문제에서 시작시간과 끝시간이 같다고 해도 된다고 했으므로 끼워넣어도 무방하다.
이러한 풀이에 따라 pair형으로 vector에 값들을 넣어주고 시작시간을 기준으로 sort한다. 역방향으로 시작시간이 늦은 회의부터 검사하므로 int형 max값을 설정하여 겹치지 않도록 조건식을 세운다.
이때, 회의시간은 int형의 최댓값보다 작거나 같다고 하였다.
그래서 INT_MAX를 이용하려했으나 백준의 c++17버전에서는 사용하지 못해 컴파일 에러가 발생하므로 직접 정수 최댓값 2147483647을 넣어야 한다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int N;
cin >> N;
vector<pair<int, int>> v;
int a, b;
for (int i = 0; i < N; i++) {
cin >> a >> b;
v.push_back(pair<int, int>(a, b));
}
sort(v.begin(), v.end());
int max = 2147483647;
int result = 0;
for (int i = N - 1; i >= 0; i--) {
if (v[i].second <= max) {
max = v[i].first;
result++;
}
}
cout << result;
return 0;
}
