백준 1931번 (Gold 5)

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

정렬의 조건문을 잘 설정해야 하는 문제이다.

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

int main() {
	std::vector <std::pair<unsigned int, unsigned int>> v;

	int N;
	cin >> N;

	for (int i = 0; i < N; ++i) {
		unsigned int first, second;
		cin >> first >> second;
		v.emplace_back(make_pair(first,second));
	}

	std::sort(v.begin(), v.end(), [](std::pair<unsigned int, unsigned int> l, std::pair<unsigned int, unsigned int> r) {
		if (l.second == r.second) {
			if (l.first == l.second)
				return false;
			else if (r.first == r.second)
				return true;
			return l.first > r.first;
		}
		else 
			return l.second < r.second; });

	int count = 0; 
	unsigned int start = 0;
	for (auto iter = v.begin(); iter != v.end(); ++iter) {
		if (start <= iter->first) {
			start = iter->second;
			count++;
		}
	}

	std::cout << count;


	return 0;
}

회의시간이 끝나는 그 시점이 가장 작은 회의를 우선으로 두고 정렬하면 되는 문제인데, 세세하게 조건문을 추가해줘야 한다.

끝나는 회의시간이 같다면 전체 회의시간이 더 짧은것을 우선으로 두되, 시작하자마자 끝나는 회의 즉 (2, 2)같은 회의는 우선순위를 뒤로 두어야 회의가 가능해진다. 

만약 (1,2)와 (2,2)가 있을 때, (2,2)가 더 짧다고 우선순위가 먼저 오게되면 (1,2)는 회의를 할 수 없게 된다.

(1,2)가 먼저 시작하면 (2,2)도 그 이후 바로 가능하다.