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

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

1931번: 회의실배정

그리디 알고리즘을 통해 문제를 해결하였다.

가장 많은 회의를 사용하기 위해서는 회의가 끝나는 시간이 빠른 게 들어가야 되지만, 회의 시간이 겹치면 안 된다.

즉, 회의가 빨리 끝나는 순서대로 회의를 진행하지만, 다음에 실행할 회의가 지금 진행하는 회의와 시간이 겹치면 안 된다.

 

코드

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

using namespace std;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n;
	vector<pair<int, int>> want;
	int temp1, temp2;
	int cnt = 0;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> temp1;
		cin >> temp2;
		//회의가 끝나는시간, 시작시간 순서로 pair를 만든다
		want.push_back(make_pair(temp2, temp1));
	}

	//끝나는 시간의 오름차순으로 정렬한다.
	sort(want.begin(), want.end());
	//가장 많은 회의를 고르는 경우에, 가장 먼저 끝나는 회의는 무조건 들어간다
	//가장 먼저 끝나는 회의가 현재 회의라고 한다.
	pair<int, int> current = want[0];
	cnt++;

	//다음 회의를 고르는 경우는 회의가 끝나는 시간이 빠른게 들어가야 된다.
	//하지만 현재의 회의와 시간이 겹치면 안된다.
	for (int i = 1; i < n; i++)
	{
		//다음 고를 회의가 현재 회의와 시간이 겹치면 안된다.
		if (want[i].second >= current.first)
		{
			cnt++;
			//조건을 만족한 회의를 현재 회의로 지정한다.
			current = want[i];
		}
	}

	cout << cnt;

	return 0;
}