[C++][그리디-회의실배정(1931)] pair, 정렬

백준 회의실 배정 바로가기

 

체점 현황

어렵지 않았다.

 

 

[풀이 전략]

회의 시작, 끝 시간을 pair로 묶어 vector에 넣자

1. 시작 시간 순서 기준 정렬

이렇게 하면 가장 많은 개수를 찾기가 조금 어렵다.

2. 끝 시간 순서 기준 정렬

끝 시간 기준 정렬 후 범위 내에 있는 것 선택하면 되니까 이건 가능하겠다.

 

[소스 코드]

#include <bits/stdc++.h>

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,start,end,res=0;
	vector<pair<int,int>> time;
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>start>>end;
		time.push_back(make_pair(start,end));
	}
	sort(time.begin(),time.end(),compare);
	start = 0;
	end = 0;

	for(int i=0;i<N;i++){
		if(time[i].first >= end){
			res++;
			end = time[i].second;
		}
	}
	cout<<res;
	
	return 0;
}

 

저 헤더 파일 하나로 다 처리가 되니까 편하다.

아니였으면 util에 algorithm에 vector에 기타 등등 써야했을텐데

 

어차피 끝 시간을 기준으로 정렬이 되어있는 상태기 때문에 전에 선택한 회의 끝 시간과

선택할 회의 시작 시간을 비교하면 끝이다.