[G5] 백준 11000번 강의실 배정 C++ 우선순위 큐

리뷰

 

우선순위 큐 두개를 사용해서 문제를 풀었다.

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

 

전역 변수

• n, ans : 강의의 개수를 저장할 정수형 변수 n, 정답을 저장하고 출력할 정수형 변수 ans
• Ing : 현재 진행중인 강의 정보를 저장할 구조체, 1순위로 종료시간, 2순위로 시작시간 오름차순 정렬해 준다.
• Stay : 아직 대기중인 강의 정보를 저장할 구조체, 1순위로 시작시간, 2순위로 종료시간 오름차순 정렬해 준다.

 

함수

1. Ing Compare

bool operator<(const Ing& other)

 

t를 기준으로 오름차순, t가 동일하다면 s를 기준으로 오름차순 정렬해 준다.

 

2. Stay Compare

bool operator<(const Stay& other)

 

s를 기준으로 오름차순, s가 동일하다면 t를 기준으로 오름차순 정렬해 준다.

 

 

문제풀이

1. n을 입력받고, Ing, Stay타입 우선순위 큐를 각각 pq1, pq2로 초기화 해준다.
2. 강의의 시작 시간과 종료 시간을 입력 받고 pq2에 push해준다.
3. pq2가 빌때까지 반복을 하며 가장 top에 있는 Stay구조체를 꺼내와 시작 시간과 종료 시간을 초기화 한다.
4. 만약 pq1이 비지 않았고, pq1의 top에 있는 종료시간이 현재 강의의 시작시간보다 작거나 같을경우 pq1에서 빼준다.
5. pq1에 현재 강의 정보를 넣어주고 ans에 pq1의 사이즈로 최대값을 갱신해 준다.
6. 모든 탐색을 마친 후에 ans값을 출력해 준다.

 

참고 사항

• 시작시간 및 종료시간 모두 오름차순 정렬이므로 pair를 통해 우선순위 큐를 사용해 주어도 된다.
• 만약 pair를 사용하고자 한다면 현재 강의가 진행중인 정보를 담은 우선순위큐는 t, s순으로 인자를 넣어줘야 한다.

 

정답 코드

#include<iostream>
#include<queue>

using namespace std;
int n, ans;

struct Ing {
	int s, t;
	bool operator<(const Ing& other) const {
		if (t > other.t) return true;
		if (t < other.t) return false;
		if (s > other.s) return true;
		if (s < other.s) return false;
		return false;
	}
};

struct Stay {
	int s, t;
	bool operator<(const Stay& other) const {
		if (s > other.s) return true;
		if (s < other.s) return false;
		if (t > other.t) return true;
		if (t < other.t) return false;
		return false;
	}
};

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

	cin >> n;
	priority_queue<Ing> pq1;
	priority_queue<Stay> pq2;
	for (int i = 0; i < n; i++) {
		int s, t; cin >> s >> t;
		pq2.push({ s, t });
	}
	while (!pq2.empty()) {
		Stay stay = pq2.top(); pq2.pop();
		int s = stay.s, t = stay.t;
		while (!pq1.empty() && pq1.top().t <= s) pq1.pop();
		pq1.push({ s, t });
		ans = max(ans, (int)pq1.size());
		
	}
	cout << ans;
}