알고리즘(C++) / 백준 1931 : 회의실 배정

1931

www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

 

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

코드

//1931 회의실 배정
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int main() {
	int N;
	vector <pair<int, int>> meeting;

	cin >> N;
	pair<int, int> meet;
	for (int i = 0; i < N; i++) {
		cin >> meet.second >> meet.first; //끝나는 시간을 기준으로 정렬
		meeting.push_back(meet);
	}

	sort(meeting.begin(), meeting.end()); //오름차순정렬

	int count = 0;
	int compare = 0;
	int start, end;
	for (int i = 0; i < N; i++) {
		start = meeting[i].second;
		end = meeting[i].first;
		if (compare <= start){
			compare = end;
			count++;
		}
	}

	cout << count << endl;

	return 0;
}

 

설명

meeting 변수는 vector로 pair쌍으로 저장하고 있다. first에는 끝나는시간을 second에는 시작 시간을 입력받는다. first에 입력받는 이유는 끝나는 시간을 기준으로 오름차순 정렬하기 위해서이다.

입력받은 meeting 벡터를 끝나는 시간 기준으로 오름차순 정렬한다.

* 이때 정렬은 pair의 first를 기준으로 오름차순으로 정렬된다. first가 같다면 second가 작은 순서대로 정렬된다.

회의의 최대 개수가 되기 위해서는 강의가 끝나는 시간이 최대한 빨라야한다. 

해결 - 끝나는 시간이 빠른 회의를 선택하고 끝나는 시간보다 같거나 큰 수 중 끝나는 시간이 가장 빠른 회의를 선택한다.

정렬할 때 끝나는 시간이 빠른 순서대로 정렬하고 끝나는 시간이 같다면 시작 시간이 빠른 순서대로 정렬되기 때문에 다음과 같이 구현이 가능하다.

 

결과

 

고찰

처음 문제를 풀 때 저번에 풀었던 문제인 11000 강의실 배정과 비슷한 문제로 생각하여 문제를 풀었다. 하지만 강의실 배정 문제와는 약간 조건이 달랐다. 강의실 배정은 모든 수업을 배정해야 하지만, 이번 문제는 모든 회의를 배정하지 않고 최대로 사용할 수 있는 회의의 최대 개수를 출력하는 것이다. 그래서 빨리 끝나는 시간대로 정렬하여 시작시간과 끝나는 시간을 비교하여 문제를 풀 수 있었다.

 

난이도

●●○○○