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

회의 시간에 대한 문제는 그리디 알고리즘의 대표적인 문제라고 한다.

회의 시간이 끝나는 시간을 기준으로 정렬 한 후, 현재 기준에서 가능한 회의 가장 회의가 빨리 끝나는 것을 고르면 된다.

 

끝나는 시간이 같은 경우가 있을 수 있는데 

(6, 8)

(8, 8)

이러한 경우이다. 이런 경우를 고려하여 정렬을 해줘야 한다. 

만약 끝나는 시간이 같다면 시작시간을 기준으로 정렬해주면 된다.

 

회의 시간 정렬이 끝나면, 맨 처음 시작 시간을 기준으로 차례대로 카운트 해나가면 원하는 값을 구할 수 있다. 

 

코드는 다음과 같다. 벡터를 이용하여 회의 시간을 담아 정렬을 하였다.

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

struct Time
{
	int begin;
	int end;
};

bool cmp(Time f, Time s)
{
	if (f.end == s.end)
		return f.begin < s.begin;
	else
		return f.end < s.end;
}

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

	vector<Time> t(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> t[i].begin >> t[i].end;
	}

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

	int cnt = 0;
	int n = 0;

	for (int i = 0; i < t.size(); ++i)
	{
		if (n <= t[i].begin)
		{
			n = t[i].end;
			++cnt;
		}
	}

	cout << cnt << endl;
}