취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11000번 문제인 강의실 배정이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11000

문제에서 주어진 조건을 잘 살펴보자.

모든 수업은 시작하는 시간이 끝나는 시간보다 앞서는 것을 알 수 있다.

현재 시간에 진행되는 수업의 수를 cnt라 하자. cnt의 초기값은 0이다.

관찰을 통해, 모든 수업시간의 시작시간과 끝 시간들을 정렬한 다음, 어떤 하나의 수업시작 시간을 만나면 현재 시점에서 cnt가 1 늘어나고, 수업 끝 시간을 만나면 현재 시점에서 cnt가 1 줄어든다는 것을 알 수 있다.

가장 많은 강의실을 필요로 하는 순간은 cnt가 최대인 순간이 될 것이라는 것을 알 수 있다.

cnt를 계산하는 과정에서 주의해야하는 점이 하나 있다. 바로 어떤 한 시간에 여러 수업이 동시에 시작하고 끝나는 경우이다. 이 경우, 끝나는 수업을 먼저 처리하고 나중에 시작하는 수업을 처리해야한다. 시작하는 수업과 끝나는 수업이 동시에 있을 때 시작하는 수업을 먼저 계산하고 현재 진행중인 수업의 수를 세면 실제보다 현재 진행되는 수업의 수보다 많은 수업의 수를 순간 cnt가 갖고 있게 되기 때문이다.

이를 쉽게 해결하기 위해, 글쓴이는 수업의 시작시간과 끝시간을 각 배열로 만들어 두 배열의 index를 관리하여 문제를 해결하였다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>

using namespace std;
int S[200000];
int E[200000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> S[i] >> E[i];
	}

	sort(S, S + N);
	sort(E, E + N);

	int mx = 0;
	int cnt = 0;
	int sidx = 0;
	int eidx = 0;

	while (sidx < N) {
		if (S[sidx] < E[eidx]) {
			cnt++;
			sidx++;
			if (mx < cnt) mx = cnt;
		}
		else {
			cnt--;
			eidx++;
		}
	}

	cout << mx;
}