[백준] 1374번. 강의실 (C++)

문제

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

 

풀이

INPUT

강의 번호는 상관이 없다.

timeTable에 시작,종료시간 정보를

시작 시간 기준 오름차순 정렬한다.

 

CHECK

priority_queue endTime은 수업이 빨리 끝나는 순으로 정렬되어 있다

 

timeTable의 i번째 수업 시작시간이

endTime내의 가장 빨리 끝나는 시간 이후에 시작된다면

방을 추가할 필요가 없다. 

그리고 해당 방의 수업 종료 시간은 i번째 수업 종료시간으로 갱신되야 하므로

endTime.pop()을 해준다.

 

timeTable의 i번째 수업 시작시간이

endTime내 가장 빨리 끝나는 시간 이전에 시작이라면

해당 방에서는 수업을 할 수 없으니 방을 추가한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int main()
{
	//INPUT
	int N, LectureN, StartT, EndT;
	vector<pair<int, int>> timeTable;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> LectureN >> StartT >> EndT;
		timeTable.push_back({ StartT,EndT });
	}
	sort(timeTable.begin(), timeTable.end());//수업 시작 시간 기준 정렬


	//CHECK
	int room = 1;
	priority_queue<int, vector<int>, greater<int>>endTime;//가장 빠르게 끝나는 수업 시간 확인
	for (int i = 0; i < N; i++)
	{
		int start = timeTable[i].first;
		int end = timeTable[i].second;

		if (!endTime.empty())
		{
			if (endTime.top() <= start) //종료시간이 i번째 수업 시작시간보다 빠르면
			{ endTime.pop(); }//방 추가 필요없음
			else { room++; }//아니라면 방 추가
		}
		endTime.push(end);
	}
	cout << room;
}