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

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 그리디 알고리즘 문제로, 주어진 회의들 중 시간대가 겹치지 않는 선에서 가능한 회의들을 선택했을 때 그 개수가 최대인 경우를 구해야 한다.

1) conferences 벡터에 주어진 각 회의들의 시작 시각과 종료 시각을 pair로 삽입한다.

2) 위 벡터를 회의 시작 시각의 오름차순으로 정렬하고, 회의 시작 시간이 같은 케이스는 종료 시각의 오름차순으로 정렬한다.

3) 직전 회의의 시작 시각, 종료 시각을 저장하는 start와 end를 선언하고 처음에는 둘 다 0으로 초기화한다.

4) conferences 벡터의 각 원소들을 차례대로 탐색하면서 가장 많은 개수의 회의가 실행되도록 한다.

• 현재 순서 회의의 시작 시각 < 직전 회의 종료 시각일 때
  • 현재 순서 회의의 종료 시각 <= 직전 회의 종료 시각이면 (직전 회의 시간 안에 들어가는 경우)
    • 직전 회의보다 시간을 덜 차지하므로 다른 회의들이 들어올 수 있는 시간을 확보할 수 있음. 따라서 회의 목록에서 직전 회의를 취소하고 현재 순서 회의를 넣는다.
      • start와 end를 현재 순서 회의의 시작 시각과 종료 시각으로 초기화
• 현재 순서 회의의 시작 시각 >= 직전 회의 종료 시각일 때
  • 직전 회의와 겹치는 시간 없으므로 직전 회의 다음으로 가능한 회의 -> count 1 증가
    • start와 end를 현재 순서 회의의 시작 시각과 종료 시각으로 초기화

5) 벡터의 모든 원소 탐색하고 나면 count에 최대 회의 개수가 남게 되고, 이를 반환한다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;
typedef pair<int, int> pii;		// (회의 시작 시각, 끝나는 시각) 저장

bool Compare(pii confA, pii confB)
{
	if (confA.first == confB.first)
		return confA.second < confB.second;
	else
		return confA.first < confB.first;
}

int solution(vector<pii> confs)
{
	int count = 0;
	int start = 0, end = 0;
	for (int i = 0; i < confs.size(); i++)
	{
		if (confs[i].first < end)		// (이번 순서 회의의 시작 시각 < 이전에 저장된 회의의 종료 시각)일 때  
		{
			if (confs[i].second <= end)	// (이번 순서 회의의 종료 시각 <= 이전에 저장된 회의의 종료 시각)이면
			{
				start = confs[i].first;	// 이전 회의를 취소하고 이번 순서 회의를 넣어 가장 최근 회의로 갱신
				end = confs[i].second;
			}
		}
		else if (confs[i].first >= end)	// (이번 순서 회의 시작 시각 >= 이전에 저장된 회의의 종료 시각)일 때
		{								
			count++;					// 겹치는 시간 없으므로 가능한 회의 -> count 1 증가
			start = confs[i].first;		// 이번 순서 회의를 가장 최근 회의로 갱신
			end = confs[i].second;
		}
	}
	return count;
}

int main(void) 
{
	ios::sync_with_stdio(false);
	cin.tie(); cout.tie();

	int n;
	cin >> n;

	vector<pii> conferences;
	for (int i = 0; i < n; i++)
	{
		int start, end;
		cin >> start >> end;

		conferences.push_back(pii(start, end));
	}

	sort(conferences.begin(), conferences.end(), Compare);	// 회의 시작 시각 오름차순으로 정렬, 시작 시간이 같은 케이스는 종료 시각 오름차순으로 정렬
	cout << solution(conferences);
}