[Silver I] 1931번 회의실 배정

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

1931번: 회의실 배정

 

이 문제는 그리디 알고리즘을 활용해야한다.

회의의 시작 시간과 다음 회의의 끝나는 시간을 비교하여 시작 시간이 작거나 같으면 선택 가능한 회의 수를 증가시킨다.

그 다음 순회를 위한 시작 시간을 선택된 회의의 시작 시간으로 변경한다.

 

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

int N;
int dp[1001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N;
	vector<pair<int,int>> v;
	int s, e;
	for (int i = 0; i < N; i++) {
		cin >> s >> e;
		v.push_back(make_pair(e,s));
	}
	sort(v.begin(), v.end());

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