백준 1931 : 회의실 배정

문제 설명

---

 여러 회의의 시작시간과 끝나는 시간이 주어졌을 때, 최대 사용할 수 있는 회의의 최대 개수를 출력한다. (총 회의의 수 ≤ 100,000)

---

 

 이 문제는 그리디 알고리즘을 이용하여 풀 수 있다. 회의들의 시작 시간과 종료 시간을 바탕으로 최대한 많은 회의를 진행할 수있게 하려면 끝나는 시간을 기준으로 정렬하는 것이 좋다. 이를 알기 위해서는 입출력 예를 수직선에 그려보는 것이 좋다. 

---

입력 예

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

를 수직선상에 나타내면

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
|----|
  |----|
|------|
      |----|
  |--------|
      |------|
        |------|
            |------|
            |--------|
    |---------|
                |-----|

와 같이 나타낼 수 있다. 회의의 시작시간을 기준으로 오름차순 순차탐색을 한다면, "회의의 시작시간은 더빠르지만 끝 시간이 더 길다"와 같은 반례가 나오기 때문에, 회의의 종료 시간기준 오름차순에서 순차탐색을 통해 답을 구해내야한다.

---

소스 코드

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector <pair<int, int>> vec;

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		int s, e;
		scanf("%d %d", &s, &e);
		vec.push_back({ e, s });
	}
	sort(vec.begin(), vec.end());
	int time = vec[0].first;
	int ans = 1;
	for (i = 1; i < n; i++) {
		if (time > vec[i].second) continue;
		time = vec[i].first;
		ans++;
	}
	printf("%d", ans);
	return 0;
}