[C++] 백준 11000번: 강의실 배정

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

11000번: 강의실 배정

 

중요풀이

그리디 알고리즘 활용에서 시간을 단축하기 위해 입력된 벡터를 O(N)의 시간복잡도만 확인하여

조건을 확인해보는 방법을 생각해봐야합니다.

우선적으로 받음 입력을 시작, 끝 시간 순으로 정렬을 시켜줍니다.

이후 벡터에서 꺼내 시간을 이동한다고 생각하여 중복되는 시간들의 수를 체크해줍니다.

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

using namespace std;

bool compare(pair<int, int> a, pair<int, int>b) {
	if (a.first == b.first) return a.second < b.second;
	else
		return a.first < b.first;
}

int main() {
	ios_base::sync_with_stdio(false);
	cout.tie();
	cin.tie();

	int N, S, T, answer = 0;
	vector<pair<int, int>>v;
	priority_queue<int>pq;

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> S >> T;
		v.push_back({ S,T });
	}

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

	for (int i = 0; i < v.size(); i++) {
		pq.push(-v[i].second);// 입력을 오름차순으로 하기위해 음수화
		int temp = -pq.top();
		if (temp <= v[i].first) {
			pq.pop();
			while(!pq.empty()) {// 다음 순위 시간 때가 끝났는지를 연속적으로 확인
				if (temp == -pq.top())
					pq.pop();
				else
					break;
			}
		}
		if (pq.size() > answer)// 현재를 확인하면 우선순위 큐에 들어있는 시간을 수업이 동시 진행이라고 생각
			answer = pq.size();
	}

	cout << answer;

	return 0;
}