[백준] 회의실 배정

bin1225·2022년 11월 27일
0

c++ 알고리즘

목록 보기
28/35

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool compare(pair<int,int> a, pair<int,int> b){
	if(a.second==b.second) return a.first<b.first;
	return a.second < b.second;
}

int main(){
	
	int n, s, e;
	cin>>n;
	vector<pair<int,int>> startEndTime;
	
	for(int i=0; i<n; i++){
		cin>>s>>e;
		startEndTime.push_back(make_pair(s,e));
	}
	
	sort(startEndTime.begin(), startEndTime.end(),compare);

	int answer = 0;
	int last = 0;
	for(int i=0; i<startEndTime.size(); i++){
		if(startEndTime[i].first >= last){
			answer++;
			last = startEndTime[i].second;
		}	
	}
	
	cout<<answer;
}

학교에서 그리디 알고리즘을 배울 때 접한 적이 있는 문제였기 때문에 생각하는데 오래 걸리지 않았다.

결국 최대한 많이 회의실을 이용하도록 하기 위해서는 가능하다면 끝나는 시간이 빠른 순서대로 배정하는 것이 가장 최적의 방법이다.

조금 디테일이 추가된 것이 끝나는 시간과 시작 시간이 동일한 경우가 주어지는 것인데, 처음에는 종료시간이 같은 경우 시작시간은 상관없다고 생각해서 따로 정렬하지 않았는데, 이 케이스 때문에 정렬을 해주어야 했었다.

2개의 댓글

comment-user-thumbnail
2022년 11월 27일

올~ 요즘 열심히 하는데?? ㅋㅋㅋㅋ 나랑 비슷한 포스트 제목이랑 태그네ㅎㅎㅎ

1개의 답글