[99클럽/코딩테스트 챌린지/C++] 최소 강의실 문제 해결 과정

문제 링크 :

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

문제 요약

이 문제는 N개의 강의를 최소한의 강의실 개수로 배정하는 것이 목표입니다. 강의실은 동시에 두 개 이상의 강의를 진행할 수 없지만, 한 강의의 종료 시간과 다른 강의의 시작 시간이 겹치는 것은 허용됩니다.

조건:

• 각 강의는 시작 시간과 종료 시간을 가집니다.
• 한 강의실에서 동시에 두 개 이상의 강의를 진행할 수 없습니다.
• 주어진 강의 정보를 기반으로 필요한 최소 강의실 개수를 구해야 합니다.

접근법

이 문제는 그리디 알고리즘과 우선순위 큐를 사용하여 효율적으로 해결할 수 있습니다. 접근 과정은 다음과 같습니다:

 

1, 강의 정렬:

• 강의는 시작 시간을 기준으로 정렬합니다. 시작 시간 기준으로 정렬하면, 강의 배정을 순차적으로 진행할 수 있습니다.

2, 우선순위 큐를 사용한 종료 시간 관리:

• 종료 시간이 가장 빠른 강의부터 관리하기 위해 최소 힙(우선순위 큐)을 사용합니다.
• 종료 시간이 가장 빠른 강의와 현재 배정하려는 강의의 시작 시간을 비교하여 강의실을 재사용할지, 새로운 강의실을 추가할지 결정합니다.

3, 겹치지 않는 강의 배정:

• 새로운 강의의 시작 시간이 현재 가장 빠르게 끝나는 강의의 종료 시간보다 크거나 같으면, 해당 강의실을 재사용합니다.
• 그렇지 않으면 새로운 강의실을 추가합니다.

4, 우선순위 큐 크기 = 필요한 강의실 개수:

• 우선순위 큐에 남아 있는 종료 시간의 개수는 현재 사용 중인 강의실의 개수를 나타냅니다.

전체 코드

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

using namespace std;

int N = 0;
int main() {
	std::cin >> N;

	vector<tuple<int, int, int>> classes;
	for(int i = 0; i < N; i++)
	{
		int a, b, c = 0;
		std::cin >> a >> b >> c;
		classes.emplace_back(b, c, a);
	}

	sort(classes.begin(), classes.end());

	priority_queue<int,vector<int>,greater<>> current;
	for (auto c : classes)
	{
		int start = get<0>(c);
		int end = get<1>(c);
		if(current.empty())
		{
			current.push(end);
			continue;
		}
		if(current.top() <= start)
		{
			current.pop();
			current.push({end});
		}
		else
		{
			current.push({ end });
		}
	}

	std::cout << current.size() << std::endl;

    return 0;
}

배운 점

그리디 알고리즘의 적용:

• 시작 시간을 기준으로 강의를 순서대로 처리하며, 현재 가능한 선택 중 최적의 선택(종료 시간이 가장 빠른 강의실)을 하는 그리디 접근 방식이 효과적임을 배웠습니다.

우선순위 큐의 활용:

• 최소 힙을 사용하여 종료 시간이 가장 빠른 강의를 효율적으로 추적할 수 있었습니다. 이를 통해 O(Nlog⁡N)O(N \log N)O(NlogN)의 시간 복잡도로 문제를 해결할 수 있었습니다.

정렬과 효율적인 데이터 관리의 중요성:

• 강의 데이터를 시작 시간 기준으로 정렬한 뒤 종료 시간만 관리하는 방식으로, 데이터를 효율적으로 처리할 수 있다는 점을 확인했습니다.

결론

이 문제를 통해 정렬과 우선순위 큐를 활용한 효율적인 데이터 관리 기법을 학습할 수 있었습니다. 특히, 그리디 알고리즘의 핵심은 현재 가능한 최적의 선택을 통해 문제를 단계적으로 해결하는 것임을 다시 한번 깨달았습니다. 앞으로도 유사한 스케줄링 문제에서 이러한 접근 방식을 활용할 수 있을 것입니다.