1931 회의실 배정

그리디 문제인데, 회의 시간을 어떻게 정렬해서 풀어야 할지를 생각해야 한다.

나는 회의가 시작하는 시간을 기준으로 정렬해서 풀었다.
문제의 테스트 케이스를 예시로 들면

11

0 6
1 4
2 13
3 5
3 8
5 7
5 9
6 10
8 11
8 12
12 14 처럼 회의 시작 시간을 기준으로 정렬한다.

그리고 처음부터 탐색하면서
회의가 끝나는 시간이 이전 회의가 끝나는 시간보다 더 빠르다면
그 회의를 선택하고(회의 개수를 카운트하지는 않음)

그렇지 않고 회의가 시작하는 시간보다는 늦다면
회의 개수를 카운트하는 식으로 풀었다.

위의 박스 길이를 회의 시간이라고 했을 때,
그리디 방식으로 당연히 빨리 끝나는 회의를 선택하는 것이 이득이다.

코드

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

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<pair<int, int>> roomTime(n);

	for (int i = 0; i < n; i++)
		cin >> roomTime[i].first >> roomTime[i].second;


	sort(roomTime.begin(), roomTime.end());

	int finishTime = -1;
	int maxNum = 0;

	for (int i = 0; i < n; i++)
	{
		if (finishTime > roomTime[i].second)
			finishTime = roomTime[i].second;


		else
		{
			if (finishTime <= roomTime[i].first)
			{
				maxNum++;
				finishTime = roomTime[i].second;
			}
		}

	}

	cout << maxNum;


}

하지만 다른 풀이들을 보니 회의가 끝나는 시간을 기준으로 정렬해
더 간단하게 풀었다.

회의가 끝나는 시간을 기준으로 정렬하여,
처음부터 탐색해 회의가 끝나고 그 다음 회의를 진행할 수 있는 시간이면 선택하는 식으로 풀이하였다.
이게 조금 더 간단하다.

코드

#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;

	return a.second < b.second;
}

int main()
{
	int n;
	cin >> n;

	vector<pair<int, int>> roomTime(n);

	for (int i = 0; i < n; i++)
		cin >> roomTime[i].first >> roomTime[i].second;


	sort(roomTime.begin(), roomTime.end(),cmp);

	int finishTime = -1;
	int maxNum = 0;

	
	
	for (int i = 0; i < n; i++)
	{
		
			if (finishTime <= roomTime[i].first)
			{
				maxNum++;
				finishTime = roomTime[i].second;
			}
		

	}

	cout << maxNum;
	

}