[C/C++] 백준 1931, Greedy

문제

1931번: 회의실 배정 (acmicpc.net)

1931번: 회의실 배정

코드

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

using namespace std;

int main() {
	int N, s, e, sum=1;
	vector<pair<int, int>> schedule;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> s >> e;
		schedule.push_back(make_pair(e, s));
	}

	sort(schedule.begin(), schedule.end());

	int i = 0, j = 1;
	while (j < N) {
		if (schedule[i].first <= schedule[j].second) {
			i = j;
			sum++;
		}
		j++;
	}
	cout << sum;
}

풀이

1. 진행 가능한 회의의 수를 sum에 저장한다. (적어도 한 개의 회의는 가능하므로 sum=1)

2. 회의의 시작 시간과 끝나는 시간을 vector에 pair로 끝나는 시간, 시작하는 시간 순으로 저장한다. (끝나는 시간을 기준으로 오름차순 정렬하면, 끝나는 시간이 가장 빠른 회의부터 차례로 진행할 수 있음)

3. 벡터를 끝나는 시간을 기준으로 오름차순 정렬하여 차례로 다음회의의 시작 시간과 비교한다.

4. 다음 회의의 시작 시간이 현재 회의의 끝나는 시간보다 크거나 같으면 회의를 진행할 수 있으므로 sum++

5. 진행이 가능하다고 판단되는 새 회의를 기준으로 하여 다음 회의의 시작 시간과 비교한다.

6. 3~5 번을 반복한다.