[기출 중] 도서관 좌석 예약

[문제]

2개의 좌석에 대해서, 학생들의 희망 시작 시간과 희망 종료 시간이 저장된 배열이 주어질 때, 최대로 예약할 수 있는 학생의 수를 구하는 문제이다. 좌석의 우선순위는 동일하며, 한 좌석에 한 명만 앉을 수 있고, 희망 시작 시간과 종료시간이 같아도 문제없이 교대 가능하다.

 

[풀이]

그리디 알고리즘으로 풀 수 있다. 먼저 최대한 많은 학생을 배정하기 위해서는 희망 종료 시간이 짧은 순서대로 배정해주어야 하므로 정렬을 해준다. 다음 사람의 희망 시작 시간이 현재 좌석에 앉아있는 사람의 희망 종료 시간과 같거나 더 커야 교대가 가능하다. 먼저 1번 좌석이 이용 가능한지 확인해주고, 그 다음 2번 좌석이 이용 가능한지 확인한다. 이 때, 코드 상 항상 1번 좌석을 먼저 확인해주는데, 사실상 두 좌석의 우선순위는 존재하지 않으므로 1번 좌석이 이용불가능하고, 2번 좌석이 이용 가능하다면 1번 좌석에 앉은 사람을 2번 좌석으로 보내고, 1번 좌석에 새로운 사람을 앉힌다.

 

[코드]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int s[1000];
int e[1000];
vector<pair<int,int>> v;

int solution(){
	int cnt = 0;
	int finishTime1 = -1;
	int finishTime2 = -1;
	for(int i=0; i<n; i++){
		int nextTime = v[i].second;
		if(finishTime1 <= nextTime){
			cnt++;
			finishTime1 = v[i].first;
		}
		else if(finishTime2 <= nextTime){
			cnt++;
			finishTime2 = finishTime1;
			finishTime1 = v[i].first;
		}
	}
	return cnt;
}	

int main() {
	//그리디 알고리즘. 2좌석. 최대로 예약할 수 있는 학생의 수를 구하시오.
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> s[i];
	}
	for(int i=0; i<n; i++){
		cin >> e[i];
	}
	for(int i=0; i<n; i++){
		v.push_back(make_pair(e[i],s[i]));
	}
	
	sort(v.begin(), v.end());
	
	cout << solution();
	return 0;
}