11000 : 강의실 배정

풀이

일반적으로 스위핑 해서 풀면 (start == end)인 경우를 처리하기가 까다롭다.

pq를 이용해서 풀어주자.

코드

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;

int n;
pii p[200002];
priority_queue<pii> pq;

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &p[i].first, &p[i].second);
	}

	sort(p, p + n);

	for (int i = 0; i < n; i++) {
		int s = p[i].first, t = p[i].second;
		if (!pq.empty() && -pq.top().first <= s) {
			pq.pop();
		}
		pq.push({ -t,-s });
	}

	printf("%lu", pq.size());

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-02-14 22:15

Read more posts by this author