[백준]C++ 11000(강의실 배정)

#include <iostream>
#include <queue>

using namespace std;

priority_queue<pair<int, int> > Q;
priority_queue<int> Q2;


int main(void)
{
	int a=0;
	cin>>a;
	
	for(int i=0; i<a; i++)
	{
		int num1=0;
		int num2=0;
		cin>>num1>>num2;
		Q.push(make_pair(-num1,num2));
	}
	
	int count=1;
	int min=0;
	Q2.push(0);
	while(!Q.empty())
	{
		int num1=-Q.top().first;
		int num2=Q.top().second;
		Q.pop();
		
		if(num1<-Q2.top())
		{
			Q2.push(-num2);
			count++;
		}
		else
		{
			Q2.pop();
			Q2.push(-num2);
		}
		
	}
	
	cout<<count;
	
	return 0;
}

이 문제는 강의실의 갯수를 가장 적게 사용하는 것이 목표이다.

나는 우선 각 수업의 시작시간을 기준으로 우선순위 큐에 집어 넣었다.(작은게 우선이기 때문에 -를 붙여서 넣어줌)

 

그 다음 강의실에 대한 우선순위 큐를 만들었다. 강의실에 대한 큐는 수업이 가장 빨리 끝나는 강의실을 알려주는 역할을 한다. 

만약 지금 수업을 강의실에 배정해야하는데 현재 진행중인 강의실에서 가장 빨리 끝나는 수업이 새로 배정하려는 수업보다 늦다면??(예 강의실은 3시에 끝나고 새로 배정하려는 수업은 2시) 이러면 뒤에 있는 강의실은 어차피 3시보다 늦게 끝나기 때문에 볼 필요가 없다. 그럼 어떻게 해야하는가?? 강의실을 하나 더 만들어야한다. 새로운 강의실을 push해주면 된다.

위 과정을 반복해주면 끝난다.

 

이 문제를 해결하기 위해 우선순위 큐가 필요하다. 만약 배열과 for문을 사용하여 풀게되면 시간초과가 발생할 확률이 높다.(나도 처음에 for문 사용해서 시간초과 발생함 ㅋ.ㅋ)

 

-찾아보니까 우선순위 큐 사용하지 않고 백터랑 for문을 이용해서 문제 해결이 가능하다고 합니다.