[BOJ] 1931번: 회의실 배정

문제링크: 백준/BOJ https://www.acmicpc.net/problem/1931

1931번: 회의실배정

 

 비슷한 문제를 학교 과제로 풀게 되었는데 처음에는 회의가 시작하는 시간을 우선순위로 두고 정렬해서 이중 for문으로 풀려 했기 때문에 당연히 TLE가 떴다.

 

결국 이 문제는 나 혼자 힘으로 풀지 못하고 회의가 끝나는 시간을 오름차순으로 정렬해야 한다는 힌트를 보고 서야 풀 수 있었다. vector에 pair<int,int>를 넣고 algorithm 헤더에 sort 함수를 이용해서 정렬하면 자동으로 first값을 우선으로 정렬하고, 만약 first값이 같을 경우 second값을 기준으로 정렬을 해주니 아주 편했다.

 

첫번째 회의가 끝나고 다음에 올 수 있는 회의는 시작 시간이 그 전 회의의 끝나는 시간보다 같거나 그 후여야 함을 알면 문제는 끝난다. 설명이 부족한 것 같아 그림을 그렸다.

 

위에 그림은 <1,2><2,7><1,4><5,6><8,9>를 입력받은 경우를 수직선에 나타낸 것이다.

그리고 이를 앞서 한 설명대로 끝나는 시간을 우선으로 정렬하면 아래 표와 같다.

 

END	START
2	1
4	1
6	5
7	2
9	8

 

회의가 제일 먼저 끝나는 ①<1,2>의 경우 회의가 진행될 것이다.

이제 다음 타자를 정해보자.

그 다음 회의는 적어도 앞서 끝난 회의 시간보다 같거나 늦게 시작해야 한다.

또한 정렬이 회의가 일찍 끝나는 순으로 되어 있으므로 앞의 회의가 언제 끝났는지만 고려하면 바로 다음 회의를 정할 수 있다. 위 예시에서는 앞에 끝난 회의 시간이 2이기 때문에 시작 시간이 2이상인 회의를 찾는다. ②<5,6>이 이를 만족한다. <2,7>의 경우 앞에 끝난 회의 시간 6보다 시작 시간이 이르기 때문에 진행될 수 없다. ③<8,9>의 경우에는 시작 시간이 6보다 뒤이기 때문에 조건을 만족하므로 회의가 진행될 수 있다.

 

이를 구현한 코드는 아래와 같다.

 

/*
20200329
baekjoon 1931번: 회의실 배정
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	int n, ans = 1;
	vector<pair<int, int>>v;

	cin >> n;

	for (int i = 0; i < n; ++i) {
		int s, e;
		cin >> s >> e;
		//회의가 끝나는 시간 우선으로 정렬하기 위해 v의 first값으로 e를 넣음
		v.push_back({ e,s });
	}

	sort(v.begin(), v.end());

	int end = v[0].first;
	for (int i = 1; i < v.size(); ++i) {
		if (v[i].second >= end) {
			ans++;
			end = v[i].first;
		}
	}

	cout << ans;
}