[BOJ] 11000번_강의실 배정_그리디 (C++)

[문제]

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

S에서 시작해서 T에 끝나는 N개의 수업을 입력받고 최소의 강의실을 사용해서 모든 수업을 가능하게 해야할 때, 사용하는 강의실 개수를 구하는 문제이다.

[사용 알고리즘]

그리디 알고리즘

[풀이 핵심]

• 강의를 구조체를 이용해서 시작시간과 종료시간을 저장해준다.
• 강의를 시작시간이 빠른순으로 정렬해준다. (시작시간이 같으면 종료시간이 빠른순으로 정렬)
• 오름차순으로 정렬되는 우선순위 큐를 이용해서 강의실 개수를 구한다.

  1. 첫 강의가 끝나는 시간을 push한다.
  2. 두번째 강의부터 가장 빨리 끝나는 강의실(q.top)을 선택한 후에 현재 진행 중인 강의가 끝나기 전에 시작되면 강의실을 늘려주고, 아니면 현재 진행 중인 강의실에서 강의를 진행한다.
     우선순위 큐는 강의실을 저장하는 큐이므로 모든 연산이 끝난 후의 q.size()가 정답이다.

[코드]

//boj11000번_강의실 배정_그리디 알고리즘

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

using namespace std;

struct Class_Room {
	int start;
	int end;
};

bool compare(Class_Room x, Class_Room y) {
	if (x.start == y.start) {
		if (x.end < y.end) {
			return true;
		}
		else {
			return false;
		}
	}
	else {
		if (x.start < y.start) {
			return true;
		}
		else {
			return false;
		}
	}
}

int main() {
	int N;
	cin >> N;

	vector<Class_Room> v;

	for (int i = 0; i < N; i++) {
		Class_Room c;
		cin >> c.start >> c.end;
		v.push_back(c);
	}

	sort(v.begin(), v.end(), compare);

	priority_queue<int, vector<int>, greater<int>> q;
	q.push(v[0].end);

	for (int i = 1; i < v.size(); i++) {
		int start_time = v[i].start;
		int end_time = v[i].end;

		if (q.top() > start_time) {
			q.push(end_time);
		}
		else {
			q.pop();
			q.push(end_time);
		}
	}

	cout << q.size();

	return 0;
}