백준 11000 c++ "강의실 배정" -PlusUltraCode-

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

 

[필자 사고]

그리디 문제이다. 특히 정렬 관련

처음 배열을 시작순으로 정렬한뒤 매번 해당 node 를 체크하는 형식으로 문제를 해겨했다.

우선순위 큐에 매번 반복때마다 end시간을 넣어두고

매번 start시간과 비교를 하여 start시간보다 작거나 같으면 빼는 형식으로 문제를 해결했다.

이렇게 하면 마지막에 최대 필요한 강의실 수가 나온다.

[코드 해설]

1. Input() 함수
이 함수는 사용자로부터 수업의 시작 시간과 종료 시간을 입력받아 arr 벡터에 저장한다. 각 수업은 (시작시간, 종료시간) 형태의 pair<int, int>로 저장되며, 모든 입력이 끝난 후에는 시작시간을 기준으로 오름차순 정렬한다. 이 정렬을 통해 시간 순서대로 수업을 처리할 수 있게 된다.

2. Game_Start() 함수
이 함수는 최소의 강의실 개수를 구하는 핵심 로직을 담고 있다.
입력된 수업들을 순서대로 순회하며, 현재 수업의 시작 시간이 우선순위 큐(pq)의 최상단 값(즉, 가장 빨리 끝나는 수업의 종료 시간)보다 크거나 같으면, 해당 강의실을 재사용할 수 있다는 의미이므로 pq.pop()으로 제거한다.
그리고 현재 수업의 종료 시간을 pq에 넣는다.
pq는 항상 현재까지 사용 중인 강의실들의 종료 시간을 오름차순으로 유지한다.
모든 수업을 처리한 후 pq.size()는 동시에 사용되는 강의실의 최대 수, 즉 필요한 최소 강의실 수를 의미한다.

3. main() 함수
프로그램의 진입점으로, Input() 함수를 통해 데이터를 입력받고, Game_Start() 함수를 호출하여 로직을 실행한 뒤 결과를 출력한다.

[소스 코드]

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

using namespace std;

typedef pair<int, int> Node;

int N;
vector<Node> arr;
priority_queue<int, vector<int>, greater<int>> pq;
void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int s, e;
		cin >> s >> e;
		arr.push_back({ s,e });
	}

	sort(arr.begin(), arr.end());
}

void Game_Start() {
	
	for (Node node : arr) {
		int start = node.first;
		int end = node.second;

		if (!pq.empty() && pq.top() <= start) {
			pq.pop();
		}

		pq.push(end);
	}
	cout << pq.size();
}


int main(void) {
	Input();
	Game_Start();
}