[백준] 11000-강의실 배정(C++)

문제링크: https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

우선순위 큐를 사용하는 문제입니다. 

 

 

접근방식

 

1. n이 200,000까지 이기 때문에 일반적인 브루트 포스는 불가

2. 우선순위큐에 데이터를 담고 합치며 진행하는 구조를 생각

3. 우선순위큐 2개를 사용해서 구현 

 

 

문제풀이 

 

1. 입력값을을 min-heap(우선순위 큐)에 삽입

이때, 시작시간이 작은 순으로 배치

2. 시작시간이 작은 순으로 하나씩 heap에서 꺼냄

3. 두번째 min-heap2에 넣을건데,  min-heap2 top에 값의 e와 현재 데이터의 s값을 확인하고,

합칠 수 있으면 합친후 min-heap2에 삽입하는 것을 반복

4. 결과값은 min-heap2의 사이즈

 

 

아래는 정답코드입니다. 

#include <iostream>
#include <queue>
using namespace std;

int n;
priority_queue <pair<int, int>> ique;
priority_queue <pair<int, int>> oque;

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

	cin >> n;
	int a, b;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		ique.push(make_pair(-a, -b));
	}

	for (int i = 0; i < n; i++) {
		int s = ique.top().first * -1;
		int e = ique.top().second * -1;
		ique.pop();
	
		if (oque.empty()) { //처음에 비어 있다면,
			oque.push(make_pair(-e, -s));
			continue;
		}

		int ne = oque.top().first*-1;
		int ns = oque.top().second*-1;

		if (ne <= s) {
			oque.pop();
			oque.push(make_pair(-e, -ns));
		}
		else {
			oque.push(make_pair(-e, -s));
		}



	}

	cout << oque.size() << endl;

	return 0;
}