[백준 1931번/c++] 회의실 배정

알고리즘

 

• 그리디 알고리즘
• 정렬

---

풀이

시작하는 시간이 빨라도 늦게 긑나면 최대 회의의 수를 맞출 수 없으므로 각각의 스케줄에서 회의의 종료시간이 중요하게 작용한다.

 

각 회의 시작시간과 종료시간을 입력받으면

이를 종료시간을 기준으로 오름차순으로 정렬한다.

이때 종료시간이 같으면 시작시간을 기준으로 오름차순으로 정렬한다.

 

1. 첫번째 end 변수는 종료시간이 가장 빠른 스케줄의 종료시점으로 초기화한다.
2. 두번째 스케줄의 시작 지점이 첫번째 스케줄의 종료시점보다 크거나 같은지 확인한다. 크거나 같아면 cnt++ 한다.
3. 모든 스케줄을 확인할 떄 까지 2번을 반복한다.

 

---

성공 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;

struct Con{
	int s, e;
	
	Con(int s, int e){
		this->s = s;
		this->e = e;
	}
	
	bool operator < (Con &con){
		if(this->e != con.e){
			return this->e<con.e;
		} else{
			return this->s<con.s;
		}
	}
};

vector<Con> c;

int conCnt(){
	int end = c[0].e, cnt=1;
	for(int i=1; i<n; i++){
		if(c[i].s>=end){
			cnt++;
			end = c[i].e;
		}
	}
	
	return cnt;
}

int main() {
	// freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int s, e;
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> s >> e;
		c.push_back(Con(s, e));
	}
	sort(c.begin(), c.end());
	cout << conCnt();
	
	return 0;
}