[BOJ/백준 1931][C++] 회의실 배정

문제

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

 

문제 내용

회의의 시작시간과 종료시간을 입력 받아서, 회의실을 최대로 사용할 수 있는 회의의 개수를 출력하는 문제이다.

 

문제 풀이

Greedy를 사용하여 문제를 풀었다.

문제를 보고 떠올릴 수 있는 선택은 3가지 정도 있었다.
회의 시작 시간이 빠른 순서 / 회의 시간이 짧은 순서 / 회의가 빨리 끝나는 순서
각각의 경우에 대해 설명해보자면

1) 회의 시작 시간이 빠른 순서의 경우

- 회의를 아무리 빨리 시작해도 회의시간 자체가 길면 그 사이에 회의들이 여러개 들어가지 못하게 된다.

 

2) 회의 시간이 짧은 순서

- 회의 시간이 짧은 순서대로 먼저 집어넣다보면, 아래와 같은 경우가 생긴다.

 

3) 회의가 빨리 끝나는 순서

- 회의가 빨리 끝나는 순서대로 집어넣는다면, 가장 많은 개수의 회의를 집어넣을 수 있다. 집어넣을 때, 회의가 끝나는 시간이 같다면, 어느 것을 넣더라도 문제가 되지 않는다. (개수가 중요한 것이기 때문)

따라서 이 문제를 풀 때, 회의가 빨리 끝나는 순서대로 집어넣으면 된다. (greedy하게)

 

코드

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

using namespace std;
int n,a,b,cnt;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
    //입력
	cin >> n;
	vector<pair<int, int>>v;

	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		v.push_back({ b,a }); //{끝나는 시간, 시작 시간}
	}
	
    //문제 해결
	sort(v.begin(), v.end()); //오름차순으로 정렬 (끝나는시간이 빠른 순서대로 정렬됨)

	b = 0, cnt = 0;
	for (int i = 0; i < n; i++) {
		if (v[i].second < b) //시작하는 시간이 이전 것의 끝나는 시간보다 앞설 때
			continue;

		cnt++; //회의 개수 카운트
		b = v[i].first;
	}

	//결과 출력
	cout << cnt << '\n';
}

 

문제 코드 설명

1) 입력

문제의 입력형식에 따라, 처음에 회의의 개수를 입력받고, 이후에 시작 시간과 끝나는 시간을 입력받으면 된다.
다만, pair를 사용하여 {끝나는 시간, 시작 시간} 의 형태로 저장한다.

 

2) 문제 해결

sort함수를 사용하여 끝나는 시간을 기준으로 정렬을 한다.
이후, 끝나는 시간이 빠른 순서대로 회의를 집어 넣는다. (회의 개수인 cnt를 증가시킴)
이전에 추가된 회의보다 늦게 시작하면서, 끝나는 시간이 빠른 회의를 집어넣는 것이 포인트이다.