백준 1931번 회의실 배정

백준 1931번 회의실 배정 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

한 개의 회의실로 회의실 사용표를 만들려 한다.
각 회의는 시작시간과 끝나는 시간이 주어지며, 각 회의가 겹치지 않게 하면서 회의실을 사용해야 합니다.
회의는 한번 시작하면 중단할 수 없으며 끝나는 것과 동시에 다음 회의가 시작할 수 있습니다.
회의실을 사용할 수 있는 회의의 최대 개수를 찾아야합니다.
회의의 수 N(1 ≤ N ≤ 100,000)만큼 주어집니다.

문제 풀이

최대한 많은 회의가 진행되어야 하기 때문에 진행시간이 짧고, 여러 개를 순서대로 진행할 수 있어야 합니다.
여러 회의의 시간이 주어지면 회의가 일찍 끝나야 다음 회의를 또 진행함으로서 더 많은 회의를 진행할 수 있기에 시작 시간을 기준으로 정렬하는 것이 아닌 끝나는 시간을 기준으로 오름차순 정렬을 진행해줍니다.
이후 새로운 회의 시작 시간 >= 전에 회의가 끝난 시간을 순서대로 비교해주며 회의의 갯수를 찾아주면 됩니다.

전체 코드

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

using namespace std;

bool compare(vector<int> a, vector<int> b)
{
	if (a[1] < b[1])
		return true;
	else if (a[1] == b[1])
		return a[0] < b[0];
	
	return false;
}

int main()
{
	int n, answer;
	vector<vector<int>> meetings;

	cin >> n;
	meetings.assign(n, vector<int>(2, 0));

	for (int i = 0; i < n; i++)
	{
		cin >> meetings[i][0] >> meetings[i][1];
	}

	sort(meetings.begin(), meetings.end(), compare);

	answer = 0;

	int currentTime = 0;

	for (int i = 0; i < n; i++)
	{
		if (currentTime <= meetings[i][0])
		{
			currentTime = meetings[i][1];
			answer++;
		}
	}

	cout << answer;
}

출저

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