[BOJ/백준] 1931번 - 회의실 배정

 

단계별로 풀어보기 > 그리디 알고리즘 > [2단계] 1931번

 

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

1931번: 회의실 배정

 

문제 요약

1. 그리디 알고리즘을 사용하는 대표적인 스케쥴 문제

 

입력 복사

예제 입력 1 >> 출력 : 4

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

 

CODE

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define pb push_back
#define mp make_pair

typedef pair<int, int> p;
vector<p> v;

bool cmp(p a, p b) {
	if(a.second == b.second) return a.first < b.first;
	
	else return a.second < b.second;
}

int main() {
	int n;
	cin >> n;
	
	int s, f;
	for(int i=0; i<n; i++) {
		cin >> s >> f;
		v.pb(mp(s,f));
	}
	
	sort(v.begin(), v.end(), cmp); 
	
	int cnt=1;
	int ref = v[0].second;

	for(int i=1; i<n; i++) {
		if(ref <= v[i].first) {
			cnt++;
			ref = v[i].second;
		}
	}
	
	cout << cnt << endl;
}

 

문제 풀이

 

대표적인 그리디 알고리즘 문제로 일명 스케쥴 문제이다.

 

해당 문제의 해결책은 "항상 가능한 빨리 끝나는 다음 이벤트를 선택하는 것" 이다.

그렇기에 시작 시간보다 끝나는 시점에 주안점을 두어야 한다.

 

1. 끝나는 시점을 오름차순한다. (빨리 끝나는 시간 순으로 정렬됨)

2. 정렬된 첫 번째를 선택한다. 

3. 끝나는 시간과 비교해 같거나 큰 시작 시간을 탐색한다.

 

 

문제를 풀며 겪었던 어려움 및 보완할 점

 

1. pair 정렬 뿐아니라 정렬 그 자체.

2. 코드 구현이 제한적이다. → 다양한 개념을 익히고, 다른 분들의 코드 또한 많이 참고해야겠다.

 

 

잘못된 코드 XXX

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define pb push_back
#define mp make_pair

typedef pair<int, int> p;
vector<p> v;

bool cmp(p a, p b) {
	if(a.second == b.second) return a.first < b.first;
	
	else return a.second < b.second;
}

int main() {
	int n;
	cin >> n;
	
	int s, f;
	for(int i=0; i<n; i++) {
		cin >> s >> f;
		v.pb(mp(s,f));
	}
	
	sort(v.begin(), v.end(), cmp); 
	
	int cnt=1;
	int ref = v[0].second;
	
	for(auto i : v) {
		if(ref <= i.first) {
			cnt++;
			ref = i.second;
		}
	}
	
	cout << cnt << endl;
	
}

 

이미 첫번째를 선택했기에 이를 제외하고 탐색을 해야 한다!