[백준 1931] 회의실 배정

문제
한 개의 회의실에서 N개의 회의를 진행하려고 한다.
각 회의는 시작시간과 끝나는 시간이 주어져있고 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 구하라
단, 회의는 한번 시작하면 중간에 중단되지 않으면 끝나는 시간과 동시에 다음 회의가 시작될 수 있다.

입력
첫째 줄에 회의의 수 N이 주어진다.
둘째 줄부터 회의의 시작시간과 끝나는 시간이 주어진다.

출력
회의의 최대 개수 출력

---

한 개만 있는 회의실에 어떤 회의를 진행시켜야 할까?

최대한 많은 회의를 해야 하기 때문에 회의가 끝날 때마다 다음 회의는 어떤 회의를 진행시킬지 생각해봐야 한다.

문제에서 주어진 것은 시작시간과 끝나는 시간이다.

 

먼저 매번 가장 빨리 시작하는 회의를 선택하면 어떨까?

빨리 시작할 수는 있지만 가장 늦게 끝나서 하나의 회의만 할 가능성이 존재한다.

 

그렇다면 가장 짧은 시간의 회의는?

가장 짧은 시간이 소요되는 회의가 가장늦게 시작하는 경우가 생길 수 있다.

 

마지막으로 매번 가장 빨리 끝나는 회의를 선택해보자

시작시간과 상관없이 가장 빨리 끝난다면 그 다음 회의를 할 수 있는 시간이 많아지므로 가장 좋은 선택지가 될 수 있다.

 

풀이

1. 이를 위해 시작시간과 끝나는 시간이 담겨져 있는 vector를 끝나는 시간을 기준으로 오름차순 정렬한다.

2. 무조건 하나의 회의는 진행시킬 수 있고 그것이 처음 인덱스에 있는 회의이다.

3. 이 회의의 끝나는 시간을 start에 할당하고 start 이상으로 시작하는 회의를 찾는다.

4. 찾았다면 해당 회의의 끝나는 시간을 다시 start에 할당하고 최종해를 증가시킨다.

5. 위 과정을 반복한다면 최종해가 구해질 것이다. => 매 선택하는 기준을 그리디 알고리즘에 맞게 정했다.

#include "pch.h"
#include <iostream>
#include<algorithm>
#include <vector>
using namespace std;

int N;
vector<pair<int, int>> v;

bool cmp(pair<int, int> x, pair<int, int>y) {
	return x.second < y.second;
}
int main()
{
	

	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		int start, end;
		scanf("%d %d", &start, &end);
		v.push_back({ end,start});
	}

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

	int answer = 1;
	int start = v[0].first;
	for (int i = 1; i < N; i++) {
		if (v[i].second >= start) {
			start = v[i].first;
			answer += 1;
		}
	}
	
	printf("%d", answer);
	
	return 0;
}