백준 11000번 : 강의실배정 c++

코드

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

using namespace std;

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


int main(){
	int N, x, y;

	vector<pair<int, int> > lecture;
	
	cin >> N;
	
	priority_queue< int, vector<int>, greater<int> > pq;
	
	for(int i = 0; i < N; i++){
		cin >> x >> y;
		lecture.push_back(make_pair(x,y));
	}
	
	sort(lecture.begin(), lecture.end(), compare);
	
	pq.push(lecture[0].second);
	
	for(int i = 1; i < N; i++){
		pq.push(lecture[i].second);
		if(pq.top() <= lecture[i].first) pq.pop();	
	}
	
	cout << pq.size();
	
	return 0;
}

 

풀이

처음엔 N^2 짜리 코드를 짰는데, 시간초과가 나서 찾아보니 우선순위큐를 이용하는 문제였다.

처음에 강의들을 시작순서대로 배열한 뒤에

차례대로 끝나는 시간만 우선순위 큐에 넣는다.

우선순위 큐는 작은걸 맨위로 올리고 끝나는 시간이 가장 작은 친구가 맨 위에 있는데

그것보다 같거나 늦게 시작하는 친구가 오면 팝해버리고 그 친구의 끝나는 시간을 푸쉬한다.

이를 반복하면 NlogN시간 만에 끝낼 수 있네요.