[G4] 백준 30827번 회의실 배정 C++ 정렬, 멀티셋, 그리디 알고리즘

리뷰

 

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

다시는 경험하고 싶지 않은 문제

 

 

전역 변수

• N : 회의의 수의 최대값을 저장할 상수 변수
• n : 회의의 개수를 저장할 변수
• k : 회의실의 개수를 저장할 변수
• ans : 정답을 저장할 변수
• P : 시작 시간 st와 종료 시간 et를 정의할 구조체, et가 같다면 st를, 아니라면 et를 기준으로 오름차순 정렬한다.
• lst : 회의의 정보를 저장할 P타입 배열

 

함수

없음

 

 

문제풀이

1. n, k값을 입력 받고, n개의 회의 정보를 입력 받아 lst배열에 저장해 준다.
2. sort 메서드를 통해 lst배열을 operator 비교 함수를 통해 정렬을 진행해 준다.
3. 멀티셋 ms를 초기화 하고, 0을 k개 만큼 insert해준다.
4. n개의 회의 정보를 순회하며 lower_bound를 통해 현재 회의의 시작시간 이상인 이터레이터를 it에 저장한다.
5. it이 ms의 begin()이 아니고 it의 왼쪽 값이 회의의 시작시간 보다 작다면 it을 ms에서 erase해주고, 회의의 종료 시간을 ms에 insert해준 뒤  ans를 증가시킨다.
6. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. 그냥.. 모르겠다.. pq를 하나만 써도 안되고 pq의 top만 확인해 줘도 안되고 모든 회의실에 저장된 값을 뒤져 그리디하게 회의를 잘 뽑아내 주어야 한다.
2. 가장 그리디하게 뽑아내는 방법은 회의의 시작시간보다 큰 수 중 가장 작은 값의 회의를 뽑아내 주어야 한다.

 

참고 사항

• pq나 multiset을 사용할 꺼면 초기값 0을 k개 만큼 넣어주면 된다.
• size를 통해 넣을지 말지를 고민한다면 나처럼 많이 틀리게 될듯?

 

정답 코드

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

const int N = 200000;
int n, k, ans;
struct P {
	int st, et;
	bool operator<(const P& other) const {
		if (et == other.et) return st < other.st;
		return et < other.et;
	}
};
P lst[N];

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

	cin >> n >> k;
	for (int i = 0; i < n; ++i) {
		int a, b; cin >> a >> b;
		lst[i] = { a, b };
	}

	sort(lst, lst + n);
	multiset<int> ms;
	for (int i = 0; i < k; ++i) ms.insert(0);
	for (int i = 0; i < n; ++i) {
		auto it = ms.lower_bound(lst[i].st);
		if (it != ms.begin() && *--it < lst[i].st) {
			ms.erase(it);
			ms.insert(lst[i].et);
			ans++;
		}
	}
	cout << ans;
}