[BOJ] 1931번 : 회의실 배정

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n;
vector<pair<int, int>> v; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n; 
	for (int i = 0; i < n; i++) {
		int s, e; 
		cin >> s >> e;
		v.push_back({s,e});
	}
	sort(v.begin(), v.end(), [](pair<int, int>&a, pair<int, int>&b) {
		if (a.second != b.second) return a.second < b.second; 
		return a.first < b.first;
	});

	int cnt = 1, en_time = v[0].second; 
	for (int i = 1; i < n; i++) {
		if (en_time <= v[i].first) {
			cnt++; 
			en_time = v[i].second;
		}
	}
	cout << cnt << '\n';
}

greedy 알고리즘을 이용한 풀이다. vector는 각 회의시간의 시작과 끝을 담기 위해 , pair <int, int>로 정의하였고, greedy를 쓰기 위해서, 회의를 sort 해주었다. 이때, lambda함수를 이용해서 비교연산을 추가해 주었다. ( 회의 끝나는 시간이 다르다면, 먼저 끝나는 회의가 앞으로 오고, 끝나는 시간이 같다면, 먼저 시작하는 회의가 앞으로 오게 설정했다. ) 

이후, for loop를 통해, en_time과의 비교를 통해 en_time과 cnt값을 갱신해 주었다.