[강의실 배정] 강의실 배정 문제1. 최대한 많은 수의 강의 선택

강의실 배정 문제 유형

강의실 배정 문제의 유형은 크게 2가지이다.
(1) 최대한 많은 수의 강의를 배정하는 것.
(2) 최대한 강의실을 효율적으로 사용하는 것. => 최대한 많은 시간동안 강의가 진행되도록 하는 것.

강의실 배정_알고튜터

이 문제는 (1) 타입의 강의실 배정 문제이다.
이 문제의 풀이는 다음과 같다.

1) 끝나는 시간을 기준으로 강의들을 정렬한다.
2) 끝나는 시간이 가장 빠른 시간(첫번째 요소)를 시작으로 정렬된 강의들을 탐색하며 강의실 사용이 가능한 강의 숫를 카운트한다.

풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
vector<pair<int, int>> classes;

bool compare(const pair<int, int>& p1, const pair<int, int>& p2) {
	return p1.second < p2.second;
}


int solution() {
	// (0) 강의 종료 시간 기준 오름차순 정렬
	sort(classes.begin(), classes.end(), compare);	// O(NlogN)

	int endTime = classes[0].second;
	int cnt = 1;
	for (int i = 1; i < N; i++) {					// O(N)
		int nextStart = classes[i].first;
		if (endTime <= nextStart) {
			cnt++;
			endTime = classes[i].second;
		}
	}

	return cnt;
													// total: O(NlogN)의 시간복잡도
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int s, e;
		cin >> s >> e;
		classes.push_back({ s, e });
	}

	int answer = solution();
	cout << answer << endl;

	return 0;
}