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

1. 문제 이해

여러 개의 회의에 대해서 시작하는 시간과 끝나는 시간이 주어진다.
회의실은 하나인 상황에서 어떤 식으로 진행했을 때 가장 많은 회의가 진행될 수 있는지 확인하는 전형적인 탐욕적 문제

2. 소스 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n, k;
struct Meet{
	long long start;
	long long end;
};
vector <Meet> meet;
bool compare(Meet a,Meet b) {
	if (a.end == b.end)return a.start < b.start;
	return a.end < b.end;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		long long a, b;
		cin >> a >> b;
		Meet sample;
		sample.start = a;
		sample.end = b;
		meet.push_back(sample);
	}
	sort(meet.begin(), meet.end(), compare);
	int cnt = 0;
	long long middle = 0;
	cnt++;
	middle = meet[0].end;
	for (int i = 1; i < n; i++) {
		if (middle <= meet[i].start) {
			cnt++;
			middle = meet[i].end;
		}
	}
	cout << cnt << endl;
}

3. 풀이 방식

사실 처음에 이 문제에 대한 해답은 쉽게 떠오르지가 않았다.. (아마 그리디 단계라는 생각이 없었으면 진짜 별에 별 방법을 쓰면서 완전탐색으로 풀었을 가능성이 높다.)

이 문제에 가장 큰 핵심은 아래 한 줄이다.

회의가 끝나는 시간이 가장 빠른 애들 부터 차례대로 회의실을 쓰게한다 !

이말인 즉슨 -> 결국 가장 빨리 끝나는 회의를 먼저 진행해주는 방식으로 회의를 진행하다보면, 회의실을 회전율을 가장 높게 돌릴 수 있음을 의미한다.
회의 시간이 아무리 길어도 그게 가장 빨리 끝나는 회의라면? 진행해줘도 아무 상관이 없기 때문이다.

1. 빨리 끝나는 회의 순으로 Sorting 한다.
2. 진행해주는데 그다음 회의 시작시간이 끝나는 시간과 같거나 크다면 그 회의를 진행해주면 된다.

4. 얻어가는 Tip

이 문제는 정답률이 낮은 편에 속한다.
(사실 위 말만 떠오르면 정답률이 높을 것 같은 문제이기 때문이다.)

이러한 이유는 저 역시 걸렸었는데,,,
바로 코너 케이스 가 있기 때문이다.

회의는 시작되자마자 종료될 수 가 있다

이 말이 의미 하는 바는 만약 회의가 아래와 같이 두 개가 있다면

START     END
5            6
6           6

위와 같을 경우, 5 6회의가 먼저 진행된 이후 6 6회의가 진행되어야 한다는 말이다 !!
즉, 아무 생각 없이 END 순으로만 SORT 를 해버리면 운이 좋지 않을 경우 위 케이스에서 걸릴 수 있다.

이렇게 문제에 코너 케이스에 대해서 조금 더 신경 쓸 수 있는 힘이 필요하다는 것을 배워간다.