[c++] 백준 1931 회의실 배정

백준 단계별로 풀어보기[그리디 알고리즘] 회의실 배정

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

1931번: 회의실 배정

 

[풀이]

회의실 배정은 끝나는 시간이 빠른 순으로 배정해주어야 최대 배정이 가능하다. 끝나는 시간이 빠른 순으로 정렬을 해주되, 같다면 시작 시간이 빠른 회의가 앞에 위치하도록 한다.

그 다음 회의의 시작 시간이 현재 회의의 끝나는 시간과 같거나 더 늦어야 하고, 조건을 만족한다면 회의가 끝나는 시간을 변경해준다. 회의실 배정을 새로 해줄 때마다 cnt 값을 증가시켜준다.

 

[코드]

#include <iostream>
#include <algorithm>

using namespace std;

bool cmp(const pair<int, int>& p1, const pair<int, int>& p2) {
	if (p1.second == p2.second)
		return p1.first < p2.first;
	else
		return p1.second < p2.second;
}

int main() {
	//그리디.
	int n;
	cin >> n;
	int start, end;
	vector<pair<int, int>> v;
	for (int i = 0; i < n; i++) {
		cin >> start >> end;
		pair<int, int> p = make_pair(start, end);
		v.push_back(p);
	}

	sort(v.begin(), v.end(), cmp);
	
	int fin = v[0].second;
	int cnt = 1;

	for (int i = 1; i < v.size(); i++) {
		int next = v[i].first;
		if (next >= fin) {
			cnt++;
			fin = v[i].second;
		}
	}

	cout << cnt;

	return 0;
}