[백준] 1931: 회의실 배정

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력 1

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력 1

4

풀이

(1) 가장 끝나는 시간이 빠른 회의 1개를 배정한다.
(2) 1번의 회의 끝나는 시간과 다음 회의의 시작 시간을 비교해서 회의를 배정한다.
(3) 새로운 회의가 배정되면 회의 끝나는 시간을 업데이트 해준다.
(4) 2 ~ 3번의 과정을 반복한다.

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

using namespace std;

int main()
{
	vector<pair<int, int>> Schedules;
	
	int InputCount = 0;
	cin >> InputCount;

	for (int i = 0; i < InputCount; i++)
	{
		int Begin, End;
		cin >> Begin >> End;
		Schedules.push_back(make_pair( End, Begin ));
	}

	sort(Schedules.begin(), Schedules.end());

	int ClassCount = 1;
	int Time = Schedules[0].first;

	for (int j = 1; j < InputCount; j++)
	{
		if (Time <= Schedules[j].second)
		{
			ClassCount++;
			Time = Schedules[j].first;
		}
	}

	cout << ClassCount;
}