백준 1931번 - 회의실 배정(C++)

https://www.acmicpc.net/problem/1931

 

회의실 배정 문제는 아주 유명한 그리디 문제라고 한다. 그런데 이것을 아직도 안풀어봤다 ㅎ 이전에 다른 그리디 문제를 접했는데 그 문제가 이 문제를 응용한 것이라해서 풀어봤는데 잘 느낌이 안왔다.

 

아무튼 이 문제는 https://www.acmicpc.net/problem/11000 강의실 배정 문제와 비슷한 입력을 받기 때문에 우선순위큐를 떠올릴수도 있다. 그러나 우선순위큐 문제는 아니다. 무언가 최소로 사용하는 문제가 아니기 때문이다.

 

아이디어

먼저 회의를 아주 많이 하기 위해선 어떤 회의를 진행해야할지 고민해보자. 그렇다. 빨리 끝나는 회의들로 구성해야한다. 여기서 시간이 짧은 회의를 하면 안되나요? 라고 할 수 있는데 만약 

 

1 2 / 8 9  / 11 12 회의들이 있다면 이 회의들이 가능한 회의로 들어갈 것이고 그렇다면 저 우주같은 공강시간을 낭비하게 된다. 그래서 빨리 끝나는 회의를 먼저 Greedy 하게 채워나간다.

그리고 끝나는 시간이 같은 회의라면 빨리 시작하는 것을 먼저 진행한다. 어라 왜일까? 2 3 / 3 6 / 4 6 이 있다면 4 6을 하는게 더 시간을 절약할 수 있지 않나? 반례는 다음과 같다.

 

3
4 4
3 4
2 4

 

시작하자마자 끝나는 회의가 있을 수 있기 때문이다. 늦게시작하는 것을 가정하면 4 4 가 먼저 시작된다. 그러나 발리시작하게 하면 2 4 4 4 로 두개의 회의를 진행할 수 있다. 

 

우선순위큐를 사용하면 좀 더 최적화할 수 있지만 이 문제의 아이덴티티는 그리디이기 때문에 너무 집착하지 않아도 된다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool cmp(pair<int, int>& a, pair<int, int>& b){
	if(a.second == b.second) return a.first < b.first;
	else return a.second < b.second;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N; cin >> N;

	vector<pair<int, int>> arr(N);

	for(int i = 0; i < N; i++){
		cin >> arr[i].first >> arr[i].second;
	}

	sort(arr.begin(), arr.end(), cmp);
	int answer = 1;
	int endTime = arr[0].second;

	for(int i = 1; i < N; i++){
		if(endTime <= arr[i].first){
			answer++;
			endTime = arr[i].second;
		}
	}

	cout << answer << '\n';
}