[BOJ/C++] 11000(강의실 배정)

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

• dp로 풀고 싶었으나, 1e9만큼의 배열을 생성해야 하므로 해당 방법은 조건상 잘못된 풀이입니다.
• 추가로 해당 문제는 가짓수만 따진 문제입니다. 고로 최종 우선순위 큐에 남은 목록들을 보면 실제 원하는 목록과는 상이하게 되므로 이 점 생각해서 다시 풀 예정입니다.

1. 최소의 강의실을 사용하여 모든 수업 -> DP
2. s, t의 범위 <= 1e9 -> DP 안 됨, 정렬 후 우선순위 큐 예상

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define p pair<int, int>
#define s first
#define e second

int n;
p lecture[200000];

void input() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> lecture[i].s >> lecture[i].e;
	}
}

void solution() {
	input();
	sort(lecture, lecture + n);
	priority_queue<int> pq;
	pq.push(-lecture[0].e);
	for (int i = 1; i < n; ++i) {
		int st = -lecture[i].s;
		int en = -lecture[i].e;
		if (-pq.top() > -st) {
			pq.push(en);
		}
		else {
			pq.pop();
			pq.push(en);
		}
	}
	cout << pq.size();
}

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