[G5] 백준 19598번 최소 회의실 개수 C++ 정렬, 멀티셋, 그리디 알고리즘, 이분 탐색

리뷰

 

https://www.acmicpc.net/problem/19598

회의실의 개수와 관련된 문제들은 일반적인 회의실 문제와 좀 다른 것 같다.

 

 

전역 변수

• n : 회의의 개수를 저장할 변수
• lst : 회의의 시작과 종료 시간을 저장할 배열

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, n개의 회의의 시작과 종료 시간을 lst배열에 입력 받는다. 이 때 종료시간을 앞에 저장해 준다.
2. lst배열을 오름차순으로 정렬해 준다, 종료 시간 기준으로 오름차순 되어야 한다.
3. 멀티셋 dic을 초기화 해주고, 정답을 저장할 변수 ans를 0으로 초기화 해준다.
4. n개의 회의 정보를 순회하며 현재 회의의 시작 시간을 기준으로 dic에서 upper_bound해준다.
5. 반환된 이터레이터가 dic의 begin()이라면 dic에 현재 회의의 종료시간을 insert해준다.
6. 아니라면 it의 앞쪽 요소를 erase해주고, 현재 회의의 종료 시간을 insert해준다.
7. ans에 ans와 dic의 size중 큰 값을 저장해 준다.
8. 모든 회의 순회를 마친 경우 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. 그냥 종료시간을 기준으로 정렬하고 시작시간 기준으로 정렬하는 우선순위 큐 하나로 접근했다가 Fail을 받았다.
2. 종료할 회의를 선택할 때 그리디한 선택이 추가가 되어야 한다.

 

참고 사항

• upper_bound로 현재 회의의 시작 시간보다 더 큰 값 중 가장 근접한 값을 구해주었다.
• 그 앞에 요소는 현재 회의의 종료 시간이하인 값 중 가장 큰 값이다.

 

정답 코드

#include<iostream>
#include<algorithm>
#include<set>
using namespace std;

int n;
pair<int, int> lst[100000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i) {
		int st, et; cin >> st >> et;
		lst[i] = { et, st };
	}
	sort(lst, lst + n);

	multiset<int> dic;
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		auto it = dic.upper_bound(lst[i].second);
		if (it == dic.begin()) dic.insert(lst[i].first);
		else {
			dic.erase(--it);
			dic.insert(lst[i].first);
		}
		ans = max(ans, (int)dic.size());
	}
	cout << ans;
}