1931 - 회의실 배정

문제

코드

#include <bits/stdc++.h>
using namespace std;
int s,e,n,ret=1;

bool cmp(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(){
	cin >> n;
	vector<pair<int,int>>v;
	
	for(int i = 0; i < n; i++){
		cin >> s >> e;
		v.push_back({s,e});
	}
	
	sort(v.begin(), v.end(), cmp);
	
	s = v[0].first;
	e = v[0].second;
	
	for(int i = 1; i < n; i++){
		if(v[i].first < e) continue;
		s = v[i].first;
		e = v[i].second;
		ret++;
	}
	cout << ret << '\n';
}

풀이

입력한 시간을 하나의 막대기라 생각해보자. 막대기의 끝이 작은 순서로 쭉 정렬한 후 정렬할때마다 ret을 더해주면 최대값을 출력하게 된다.

결과

후기

어렵지 않았으나 그리디의 특성상 예외를 하나라도 처리하지 못하면 틀리는 듯 하다. cmp함수를 만드는 과정에서 a, b second 값이 같은 경우를 생각안했더니 상황에 따라 결과값이 달라지고 오답이었다. 예상 가능한 변수가 어떻게 되는지 생각을 길러야 한다고 생각이 들었다.