[백준] No.1931 - 회의실 배정 (C++)

문제

www.acmicpc.net/problem/1931

1931번: 회의실배정

 

풀이

solved.ac 난이도: 실버2

 

종만북의 그리디 알고리즘 파트에 등장하는 회의실 예약 문제와 동일한 문제.

하지만 본 문제에서는 회의의 시작시간과 끝나는 시간이 같을 수도 있기 때문에 유의하여 풀어야한다.

 

단순히 모든 경우를 탐색해보기에는 입력의 크기가 너무 크니 아래의 그리디 알고리즘으로 접근해보자.

 

항상 빨리 끝나는 회의 만을 선택하고 다음 회의로는 이전 회의와 겹치지 않는 가장 빨리 끝나는 회의를 선택하자.

 

이를 구현하기 위해서 회의의 시작 시간과 끝시간을 pair<int,int>로 저장하여 끝나는 시간을 기준으로 정렬하자.

pair의 second 값을 기준으로 정렬하기 위해 비교함수를 직접 작성하자.

 

bool Compare(const pair<int,int>& a, const pair<int,int>& b){
  return a.second < b.second;
}

 

meeting_list는 종료값을 기준으로 내림차순 정렬이 되어있기 때문에 list의 다음 값의 종료시간은 항상 현재 값보다 크거나 같다.

 

이후로는 meeting_list를 순회하여 이전 회의의 종료 시간(pre_end) 보다 시작 시간이 큰 회의를 찾는 다면 카운트를 해주고, 해당 회의의 종료 시간으로 pre_end를 업데이트 해주자.

 

하지만 해당 코드만으로는 문제를 맞출 수 없다.

왜냐하면 "회의의 시작시간과 끝나는 시간이 같을 수도 있다."는 문제의 조건이 있기 때문이다.

 

단순히 pair의 second값만을 기준으로 정렬을 하면

(2,2) (1,2) 순서로 입력을 받은 값은 순서가 변하지 않는다.

이 경우 (2,2)가 먼저 회의로 선택되어지기 때문에 (1,2)는 시작 시간이 2보다 이전이기 때문에 선택될 수 없다.

 

만약 pair의 first값도 기준으로 정렬한다면

(1,2) (2,2) 순서로 정렬되어 (1,2)가 선택된 이후에도 (2,2)는 선택될 수 있다.

 

코드