BOJ 1931번 회의실 배정

하나의 회의실을 여러 회의가 사용하는데 각각의 시작 시간과 끝나는 시간이 주어진다. 회의를 잘 스케쥴링 하여 회의실을 사용할때 최대 몇개의 회의가 회의실을 사용할수 있는지 구하는 문제이다. 

처음에 어렵게 꼬아 생각하여 시작 시간이 빠른 순서대로 정렬하고 끝나는 시간이 빠른 순서대로 정렬하여 두개를 어떻게 지지고 볶아 비교하려고 하였다.(생각해보면 다음 회의 시작 가능 여부는 이전 회의의 종료 시간에 따라 결정된다.) 

따라서 끝나는 시간을 기준으로 정렬 하여 제일 일찍 끝나는 회의를 기준으로 다음 회의 시작 시간을 결정하면 된다. 

한편 문제에서 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의 시작시간과 끝나는 시간이 같을 수도 있다.

라고 주어졌기 때문에 다음과 같은 반례가 생길 수 있다.

//반례1)
2
1 1
0 1

//out -> 2

//반례2)
3
1 3
8 8
4 8

//out -> 3

//반례3)
6
3 10
1 2
2 3
4 5
5 7
7 9

//out -> 5

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

bool orderByFinish(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()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;

	vector<pair<int, int>> meeeting;

	for(int i = 0; i < n; i++)
	{
		int start, finish;
		cin >> start >>finish;
		meeeting.push_back({ start,finish });
	}

	sort(meeeting.begin(), meeeting.end(), orderByFinish);

	int cnt = 1;
	int finish = meeeting[0].second;
	int nextStart = 0;

	for(int i = 1; i < n; i++)
	{
		if(meeeting[i].first < finish)
		{
			continue;
		}
		finish = meeeting[i].second;
		cnt++;
	}

	cout << cnt;
}