[백준] 1931 회의실 배정

문제

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

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

 

 

---

이 문제를 보고 처음엔 회의가 진행되는 시간(끝나는 시간 - 시작 시간)이 짧은 순으로 정렬하고자 했다.

하지만 이 방법으로는 최적의 해를 구할 수 없다. 

 

그래서 생각한 것이 시작 시간을 기준으로 하는 건 당연히 안되고(1-12까지 진행하는 회의가 있을 수 있으므로), 끝나는 시간이 짧은 순으로 정렬하여 답을 구하면 되겠다 생각을 했다.

 

끝나는 시간이 짧다는 것은 그만큼 뒤에 회의를 많이 배치할 수 있으므로 2번의 방법으로 최적의 해를 구할 수가 있는 것이다. (실제 끝나는 시간을 기준으로 정렬하려고 보니, 이미 문제의 입출력 예시에서 끝나는 시간 기준으로 정렬하여 입력 예시를 들었단 것을 발견했다.)

 

 

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

// second 기준으로 sort
bool sortby2(const pair<int, int> &a, const pair<int, int> &b)
{
	if (a.second != b.second) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}

int main(void)
{
	int n, temp1, temp2;
	int cnt = 0, prev=0;
	vector<pair<int, int>> v;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> temp1 >> temp2;
		v.push_back(make_pair(temp1, temp2));
	}

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

	for (int i = 0; i < n; i++) {
		if (prev <= v[i].first) {
			cnt++;
			prev = v[i].second;
		}
	}

	cout << cnt << endl;
	return 0;
}