백준 11000 _ 강의실 배정

www.acmicpc.net/problem/11000

11000번: 강의실 배정

---

✨ 내 소스 코드

#include<iostream>
#include <queue>
#include <functional>
#include <algorithm>
using namespace std;
class cmp
{
public:
	bool operator()(pair<int, int> pq1, pair<int, int> pq2)
	{
		if (pq1.first == pq2.first)
		{
			return pq1.second > pq2.second;
		}
		else
		{   
			return pq1.first > pq2.first;
		}
	}
};
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
    
	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
	priority_queue<int, vector<int>, greater<int>> p;
	int N,s,t;
	cin >> N;
    
	while (N--) {
		cin >> s >> t;
		pq.push(make_pair(s, t));
	}
	
	p.push(pq.top().second);
	pq.pop();
	while (!pq.empty()) {
		if (p.top() <= pq.top().first) {
			p.pop();
			p.push(pq.top().second);
			pq.pop();
		}
		else {
			p.push(pq.top().second);
			pq.pop();
		}
	}
    
	cout << p.size();
	
	return 0;
}

 

🙏 문제 풀이

priority_queue(우선순위 큐)를 이용하여 풀었다

#include <functional>은 greater<int>에서 발생하는 에러를 없애주기 위해 사용

 

 

pq에 시작 시간과 종료 시간을 쌍으로 넣어주면, 자동으로 정렬이 된다

 

EX) 백준의 예시를 따르면 pq에 다음과 같이 값이 정렬된다

 

 

p에 pq의 가장 위의 요소(시작시간이 가장 빠르고, 종료 시간이 가장 빠른)의 종료 시간을 넣어준다

 

EX) pq의 가장 위의 요소는 <1,3>이었기 때문에, q에 3이 들어간다

 

 

p의 가장 빠른 종료 시간이 현재 pq의 가장 빠른 시작 시간보다 크면

이어서 수업을 할 수 없다는 뜻이기 때문에 강의실을 하나 더 만들어야 된다

그렇기 때문에 p에 값을 넣어준 뒤, pq를 삭제한다

 

EX) pq.top()은 <2,4>였는데, 2는 q.top()인 3보다 작기 때문에 수업을 이어서 진행 할 수가 없다. 따라서 q에 새로 값을 추가해준다

 

 

p의 가장 빠른 종료 시간이 현재 pq의 가장 빠른 시작 시간 보다 작으면

이어서 수업을 할 수 있다는 뜻이기 때문에

p의 첫번째 요소(가장 빠른 종료 시간)을 삭제하고, pq의 가장 빠른 시작 시간의 종료 시간(pq.top().second)을 넣어준다

그리고 해당 강의는 사용 했으므로 pq에서 삭제해준다 (pq.pop())

 

EX) pq.top()은 <3,5>였는데, 3은 q.top()인 3보다 같거나 크기 때문에 수업을 이어서 진행 할 수 있다. 따라서 q.top()의 값을 5로 바꾸어 준다

 

p의 크기를 출력하면 강의실이 개수를 얻을 수 있다

 

 

⭐ 문제 풀이 결과