[백준] 1931번: 회의실 배정

역대급 난이도..

brute force 문제이다.

 

핵심은 먼저 끝나는 일부터 실행하는 것이다. 

먼저 끝나는 일부터 실행할 수 있도록, 회의 시간이 담긴 벡터를 sort해주었다.

sort할 때 compare함수를 정의해서 pair<int, int> 형인 회의들을 정렬할 수 있게 했다.

특히

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

여기서 중간에 a.second == b.second 이 부분에서 다시 분기해주지 않으면 오류가 난다. 

만약 끝나는 시간이 같이면 먼저 시작하는 것을 우선으로 해주면 된다. 

 

findNext()라는 함수를 정의해서, vector안에 있는 작업들 중 다음 실행할 작업을 고를 수 있도록 했다.

findNext()는 재귀적으로 작동해서, 마지막 일을 수행할 때까지 계속 그 다음 작업을 고른다. 

int findNext(int x){
	
	int count = 1;
	//cout << "do: (" << v[x].first << ", " << v[x].second << ")" << endl;
	
	if(x+1<v.size()){ //추가한 부 
		for(int i = x+1; i<v.size(); i++){
			// find next job to be done
			if(v[i].first >= v[x].second){
				// it's the next job to be done
				count += findNext(i);
				break;
			}
		}
	}
	return count;
}

main()에서 특징적인 점은, noStartPoint라는 걸 지정해줬다는 것이다.

만약에 모든 회의에 대해서 findNext()를 부르면 시간 초과가 되게 된다.

 

어느 경우이든, 어떤 회의(x)의 시작 시간이 벡터에 있는 다른 어떤 회의시간(y)의 마침 시간보다 같거나 크면 여기서(x) findNext()를 재귀적으로 호출해도 절대 최대회의수행횟수가 될 수 없다. 

예를 들어

1 3

2 4

6 8

9 10

이 있다면, (6 8)에서 시작을 해도 무조건 앞에 (1 3)이랑 (2 4)가 있는 경우가 최대값이 되기 때문에, (6 8)부터 findNext()를 불러내는 작업은 하나마나 그 결과가 최대값이 되지 않을 것이다. 

 

그래서 noStartPoint는 처음에 2^31-1 (가능한 최대 end값) 으로 초기화해두었다가, 

정렬된 벡터에서 첫 회의가 될 수 있는 애들의 end 시간중 제일 작은 값으로 저장한 후에, 그 값보다 늦게 start하는 애들은 findNext()를 부르지 않도록 했다. 

 

암튼 이렇게 가능한 startPoint에서부터 findNext()를 재귀적으로 호출해서 총 수행한 회의이 개수를 answer벡터에 넣어두었다가, 이 중 가장 큰 값을 출력하면 답이 완성된다.

 

최종코드

// 1931
// 가장 일찍 끝나는 순서대로
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int, int> > v;

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

int findNext(int x){
	
	int count = 1;
	
	if(x+1<v.size()){
    // v[x]가 만약 마지막 회의였다면 v[x+1]은 존재할 수 없다. 그래서 확인 필요
		for(int i = x+1; i<v.size(); i++){
			// find next job to be done
			if(v[i].first >= v[x].second){
				// it's the next job to be done
				count += findNext(i);
				break;
			}
		}
	}
	return count;
}

int main(void){

	// get inputs
	int n, start, end;
	vector<int> answer;
	
	cin >> n;
	for(int i = 0; i<n; i++){
		cin >> start >> end;
		v.push_back(make_pair(start, end));
	}
	
	sort(v.begin(), v.end(), compare);
	
	int noStartPoint = 2147483647;
	for(int i = 0; i<v.size(); i++){
		
		if(v[i].first >= noStartPoint){
			// it can't be a start point
			break;
		}
		// it's a start point
		if(noStartPoint>v[i].second){
			// set it's end time as a time that cannot be a start point
			noStartPoint = v[i].second;
			// 여기서부터 다음으로 수행될 회의를 차례대로 찾아간다.
			answer.push_back(findNext(i));
		}
	}
	
    // answer에서 최댓값 출력하기
	int largest = 0; 
	for(int i = 0; i<answer.size(); i++){
		if(answer[i]>largest){
			largest = answer[i];
		}
	}
	cout << largest << endl;
}