백준 1374 강의실(c++)

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

1374번: 강의실

<코드>

#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>lectures;
priority_queue<int,vector<int>,greater<int>>rooms;
int main()
{
	int n;
	cin>>n;
	int number, starttime,endtime;
	for(int i=0;i<n;i++)
	{
		cin>>number>>starttime>>endtime;
		lectures.push(make_pair(starttime,endtime));
	}
	rooms.push(lectures.top().second);
	lectures.pop();
	while(lectures.size())
	{
		if(rooms.top()<=lectures.top().first)
		{
			rooms.push(lectures.top().second);
			rooms.pop();
		}
		else
		{
			rooms.push(lectures.top().second);
		}
		lectures.pop();
	}
	cout<<rooms.size();
}

<풀이과정>

이 문제는 우선순위 큐를 활용한 문제이다. 강좌마다 시간이 겹치게 된다면(시작시간 = 종료시간 제외) 방을 추가해주면 된다. 그러기 위해서는 종료시간이 가장 빠른 것(second)을 우선적으로 추가해주는 우선순위 큐와 강의실은 시작시간이 가장 빠른것을 기준으로 추가해주는 우선순위 큐를 만들어주는 것이 핵심이다. while문 안에 if부분은 강좌시간이 겹치지 않으면 방의 개수를 그대로 해주고, 강좌시작시간을 갱신해주는 부분이다. 그렇지 않으면 방의 개수를 추가해주면 된다.