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

 

알고리즘 분류: 그리디 알고리즘, 정렬

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

1931번: 회의실 배정

 

【 풀이 】

 

시작 시간과 끝나는 시간 사이에 겹치는 회의 시간이 없이 사용 가능한 최대 회의 개수를 구하는 문제이다.

이는 곧 겹치지 않고 가장 최소인 회의시간들만 구하면 된다는 것인데,

입력으로 주어진 회의시간들을 시작 시간을 기준으로 정렬해야 한다.

 

그리고 시작 시간이 같다면, 같은 것끼리는 종료 시간을 기준으로 또 정렬한다.

 

또 한가지 주의해야할 점은 시작하자마자 끝나는 회의인데,

얘네들은 여러개 나와도 모두 카운트해주어야 한다.

 

자세한 풀이는 다음과 같다.

 

1. 시작 시간과 종료 시간을 pair 로 받는 t_table 벡터에 입력받는다.
2. 정렬한다.
3. 마찬가지로 시작 시간과 종료 시간을 pair 로 받는 best 벡터에 t_table[0]부터 넣는다.
4. t_table[1] 부터 검사해가면서 최소 시간을 구한다.(여기서 best와 t_table 은 인덱스를 다르게 가져간다.)
5. 만약 t_table[i] 가 시간이 더 안걸리면서, 종료 시간도 같거나 더 빠르다면 그 회의가 best 에 들어가게 된다.
6. t_table[i] 의 시작 시간이 best[idx]의 종료 시간보다 크다면 best의 인덱스를 증가시킨다.

 

 

 

 

【 코드 】

 

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

vector<pair<int, int>>t_table;
vector<pair<int, int>>best;

int main() {
	int cnt = 0;
	int idx = 0;
	int n;
	cin >> n;
	
	best.resize(100010,make_pair(-1,-1));

	for (int i = 0; i < n; i++) 	// 1번 과정
 	{
		pair<int, int>time;
		cin >> time.first >> time.second;
		t_table.push_back(time);
	}

	sort(t_table.begin(), t_table.end());	// 2번 과정

	best[0] = t_table[0];	// 3번 과정

	for (int i = 1; i < n; i++) {
		int best_time = best[idx].second - best[idx].first;
		int table_time = t_table[i].second - t_table[i].first;	// 4번 과정
		if (t_table[i].first >= best[idx].second) 	// 6번 과정
        	{
			idx++;
			best[idx] = t_table[i];
		}
		if (table_time <= best_time && 
			t_table[i].second <= best[idx].second) 	// 5번 과정
		{
			best[idx] = t_table[i];
		}
	}
	for (cnt = 0; best[cnt].first != -1; cnt++);
	cout << cnt;
	return 0;
}