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

문제링크

1931번 회의실 배정

 

정렬과 그리디를 통해 찾아낼 수 있음

회의의 시작 시간과 끝 시간이 한 쌍으로 묶이기 때문에 pair를 사용하여 풀어 줌

가장 많은 수의 회의를 하기 위해서는 시작시간 보다는 첫 회의가 끝나는 시간이 중요하기 때문에

회의 종료 시간을 토대로 정렬을 해주고 그 시간을 기준으로 하며 다음 시작 시간을 찾고

계속해서 일찍 끝나는 시간들을 찾아주면서 최대 회의를 할 수 있는 횟수를 찾아냄

 

제출코드

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

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

using namespace std;

int main()
{
	int N = 0, startT = 0, endT = 0, answer = 0;

	vector<pair<int, int>> vec;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> startT >> endT;
		// endT를 기준으로 정렬하기 위해 순서를 바꿔서 넣어줌
		vec.push_back(make_pair(endT, startT));
	}
	// 제일 일찍 끝나는 타임이 앞에 와야 최대한 많은 회의를 할 수 있음
	sort(vec.begin(), vec.end());

	int meetEndTime = vec[0].first;
	answer = 1;

	for (int i = 1; i < N; i++)
	{
		if (vec[i].second >= meetEndTime)
		{
			answer++;
			meetEndTime = vec[i].first;
		}
	}

	cout << answer;

	return 0;
}