[백준 BOJ][C++]1931번 회의실 배정 풀이: 그리디 알고리즘

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

1931번: 회의실 배정

 

 

 이 문제는 그리디 알고리즘으로 해결할 수 있습니다. 

 

 

[ 풀이 과정 ]

 

1. 종료 시각이 빠른 순으로 회의 정보 배열 정렬합니다. 

2. 반복문을 통해 이전 종료 시각보다 시작 시각이 같거나 느리면 회의이 개수 ans 증가

( 정렬했기 때문에 이전 종료 시각보다 시작 시각이 같거나 느린 회의가 자동적으로 지역적 솔루션이 됩니다. )

 

 

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>

using namespace std;

typedef pair<int, int> p;

int main(void) {

	int n;
	vector<p> meeting;  //first: 시작 시간, second: 종료 시간

	cin >> n;
	for (int i = 0; i < n; i++) {
		int start, end;
		cin >> start >> end;
		meeting.push_back({ start, end });
	}
	sort(meeting.begin(), meeting.end(),
		[](p a, p b) 
		{ 
			if (a.second == b.second)
				return a.first < b.first;
			return a.second < b.second; 
		});

	int time = meeting[0].second;
	int ans = 1;
	for (int i = 1; i < n; i++) {
		if (time <= meeting[i].first) {
			ans++;
			time = meeting[i].second;
		}
	}
	
	cout << ans;

	return 0;
}