백준 11000 - 강의실 배정

문제링크

• 백준 11000

문제설명

• N 개의 수업이 시작시간과 종료시간과 함께 주어진다.
• 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.
• 수업이 끝난 직후에 다음 수업을 같은 강의실에서 시작할 수 있다.
• 필요한 강의실의 최소 개수를 구하라

문제접근1

• 처음에 접근했던 방식은 우선순위 큐 자료구조를 활용하여 끝나는 시간을 기준으로 강의들을 최소힙 형태로 저장한 후 top 에 위치한 강의를 시작 강의로 선정하고, 이어서 들을 수 있는 강의들만을 담아 하나의 묶음을 만드는 방법이었다.
• 이어서 들을 수 없는 강의들은 다시 우선순위 큐에 담아두고 다음 사이클로 또 하나의 묶음을 만든다.
• (만들어진 묶음의 개수 = 필요한 강의실의 개수) 라고 생각하며 문제를 풀었지만 시간초과에 걸렸다.

구현(시간초과)

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

using namespace std;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int N;
	scanf("%d", &N);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> lectureTable;

	for (int i = 0; i < N; i++)
	{
		int start, end;
		scanf("%d %d", &start, &end);
		lectureTable.push(make_pair(end, start));
	}

	int ans = 0;
	while (true)
	{
		ans++;
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> remainLecture;
		pair<int, int> cLecture = lectureTable.top(); // 강의실 예약 시작 강의
		lectureTable.pop();
		// 뒤에 오는 강의들 중 시간이 맞는 강의들을 하나의 강의실에 넣는다.
		while (!lectureTable.empty())
		{
			// 같은 강의실을 이용할 수 없는 경우
			// 현재 강의가 끝나는 시간보다 다음 강의 시작 시간이 빠른 경우
			if (cLecture.first > lectureTable.top().second) 
			{
				remainLecture.push(lectureTable.top());
			}
			else // 같은 강의실을 이용할 수 있는 경우
			{
				cLecture = lectureTable.top();
			}
			lectureTable.pop();
		}
		if (remainLecture.empty()) break;
		lectureTable = remainLecture;
	}
	printf("%d\n", ans);
}

문제접근2

• 질문게시판, 구글링을 통해 풀이를 참고했다.
• 기본 자료구조는 역시 우선순위 큐 였다. 문제 풀이의 가장 큰 차이점은 우선순위 큐를 활용하는 방법에 있었다.
• 먼저, 강의는 시작시간을 기준으로 오름차순 정렬을 한다. (vector 컨테이너 활용)
• 배열을 탐색하며 각 강의가 끝나는 시간을 우선순위 큐에 담는다. -> 우선순위 큐는 강의가 끝나는 시간을 기준으로 최소힙 구조를 이룬다.
• 현재 선택된 강의의 시작시간과 우선순위 큐의 top 에 위치한 끝나는 시간을 비교하여 끝나는 시간 이후에 현재 강의가 시작된다면 해당 원소를 큐에서 지운다. -> 동일한 강의실에서 진행되던 강의를 새로운 강의로 대체하는 원리
• 강의가 대체되지 못했다는 것은 새로운 강의실을 사용하고 있다는 의미이므로 최종적으로 남은 우선순위 큐의 크기가 필요한 강의실의 수가 된다.

구현

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

using namespace std;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int N;
	scanf("%d", &N);
	vector<pair<int, int>> lectureTable;
	priority_queue<int, vector<int>, greater<int>> pq;

	for (int i = 0; i < N; i++)
	{
		int start, end;
		scanf("%d %d", &start, &end);
		lectureTable.push_back(make_pair(start, end));
	}
	sort(lectureTable.begin(), lectureTable.end()); // 시작 시간 기준 오름차순 정렬

	// 우선순위 큐(pq) 에는 강의의 끝나는 시간을 담는다.
	// 먼저 담긴 강의들은 일찍 끝나는 순서대로 새로운 강의로 대체된다.
	// 시간표가 맞지 않는 강의들은 큐에서 사라지지 않고 남아있기 때문에
	// 모든 강의에 대한 탐색을 마치고 난 후 남은 큐의 크기가 필요한 최소 강의실 수가 된다.
	for (int i = 0; i < lectureTable.size(); i++)
	{
		pq.push(lectureTable[i].second);
		if (lectureTable[i].first >= pq.top()) pq.pop();
	}
	printf("%d\n", pq.size());
}