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

서론

그리디 알고리즘.

시작시간을 기준으로 가능한 모든 경우의 수 탐색 -> 시간초과

종료시간을 기준으로 그리디 알고리즘 -> 통과

배낭문제와 함께 그리디 알고리즘의 대표적 문제.

아이디어

1. 종료시간을 기준으로 오름차순 정렬한다. 종료시간이 같다면 시작시간을 기준으로 오름차순 정렬한다.

2. 정렬한 배열에서 회의를 하나 가져오고 회의 수를 +1 해준다.

3. 정렬한 배열을 탐색하여 가져온 회의의 종료시간 이후에 회의가 시작하면 회의를 가져오고 회의 수를 +1 해준다.

4. 3을 반복한다.

구현

// c++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(pair<int, int>a, pair<int, int>b) {
	if (a.second == b.second) {
		return a.first < b.first;
	}
	else {
		return a.second < b.second;
	}
}

int main() {
	vector<pair<int, int>>v;
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back({ a,b });
	}
	sort(v.begin(), v.end(), compare);

	int cnt = 0;
	int now = v[0].second;
	for (int i = 1; i < n; i++) {
		if (v[i].first >= now) {
			cnt++;
			now = v[i].second;
		}
	}

	cout << cnt + 1;
}