0.문제

문제 링크

1. 풀이

우선 최대 N의 크기는 200000이므로 최악 시간복잡도는 $O(NlogN)$ 이하로 해결해야 한다.

맨 처음 문제를 잘못 읽어서 한 강의실에 배정할 수 있는 최대 수업 수를 선택하는 건 줄 알고 여러 번 틀렸다.

실제 문제에서 묻는 것은 주어진 모든 수업을 다 진행한다고 할 때 동시에 사용해야만 하는 강의실 수의 최댓값을 구해내는 것이다.


따라서 다음과 같이 풀이하면 될 것으로 생각하였다.

  1. 주어진 모든 수업을 시작 시간을 기준으로 오름차순 정렬한다.
  2. 이후 수업을 진행시키는데, 문제 조건에서 수업이 끝난 직후에는 다음 수업을 시작할 수 있다고 하였으므로($T_i <=S_i$) 그 전에 이미 진행중인 수업들 중 끝난 수업을 파악해 강의실에서 뺀다.
  3. 첫 번째로 시작하는 수업부터 순서대로 수업을 진행시킨다. 빈 강의실이 없을 경우 강의실의 수를 하나 추가한다.
  4. 현재 사용중인 강의실의 수를 확인해 최댓값을 저장한다.
  5. 시작하지 않은 강의가 없을 때까지 2~4를 반복한다.

수업은 시작과 끝 시간이 함께 주어지므로 pair<int,int>에 수업을 저장한다.

그리고 이를 vector<pair<int,int>>에 저장한 후 std::sort를 이용해 시작 시간 순서대로 오름차순 정렬이 가능하다.

다만 진행중인 수업들을 저장할 방법을 생각해 보아야 하는데, 단순히 std::vector에 저장해 매 수업마다 진행중인 수업 목록 전체를 순회하며 끝난 수업을 파악하는 방법은 적절하지 못하다. 그 이유는 다음과 같은데,


  • N개의 강의가 주어질 때 매 강의가 시작될 때마다 순회를 하게 되면 단순히 생각해도 시간복잡도가 $O(N^2)$이다. 이는 시간초과가 날 것이다.
  • 만약 시간 복잡도가 넉넉하다 해도, 진행중인 수업들 중 일부 수업이 종료되었을 때 std::vector에서 임의의 데이터를 삭제하는 방식은 비용이 크다(특히 컨테이너의 중간 어딘가에 존재한다면).


즉, 시간 복잡도의 관점에서 (1)데이터의 삭제가 용이한 자료구조를 선택해야 하며, (2)컨테이너 전체를 순회할 필요 없이 수업이 일찍 끝나는 순서대로 자동 정렬이 되어 있어야 한다.

이러한 관점을 기준으로 우선순위 큐(Priority_queue)를 사용하여 진행 중인 수업들을 관리하면 될 것으로 생각하였다.


2. 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>

using namespace std;

struct compare
{
	bool operator()(pair<int, int>& l, pair<int, int>& r)
	{
		if (l.second == r.second)
		{
			return l.first > r.first;
		}
		return l.second > r.second;
	}
};

priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//freopen("input.txt", "r", stdin);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int start, end;
		cin >> start >> end;
	
		q.push(make_pair(start, end));
	}
	int max = 0;
	while(!q.empty())
	{
		int start = q.top().first;
		int end = q.top().second;
		
		while (!pq.empty() && pq.top().second <= start)
		{
			pq.pop();
		}
		pq.push(q.top());
		q.pop();
		max = pq.size() > max ? pq.size() : max;
	}
	cout << max;
	
	return 0;
}

3. 결과