[C++][BOJ 11000 강의실 배정]그리디,정렬,우선순위큐

11000 강의실 배정

 

 

 

우선순위 큐를 배웠다.

단순하게 가자

우선순위 큐를 사용하기 전엔 직접 내부 for 돌며 검사했는데

우선순위 큐를 사용하니 알아서 top만 검사하면 되니까 쉽게 끝났다.

 

문제풀이

1. 시작,끝 시간 입력 받아 시작 시간 순으로 정렬, 시작 시간이 같다면 먼저 끝나는 순으로 정렬

2. 우선순위큐 오름차순 정렬 되도록 만들어 놓고

3. 맨 처음 클래스 끝나는 시간 하나 넣어준다.

4. for 돌며 q의 top( 가장 먼저 끝나는 수업) 과 비교해서 안겹치면 그 수업의 끝나는 시간 갱신, 겹친다면 push

 

소스코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct node{	int s,e;};
int n;
node times[200000];

bool compare(node a, node b){
	return (a.s==b.s)?  a.e<b.e : a.s<b.s ;
}


int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i = 0 ; i < n; i++){
		cin>>times[i].s>>times[i].e;
	}
	
	sort(times,times+n,compare);
	
	priority_queue<int , vector<int>, greater<int>> q;//오름차순
	q.push(times[0].e);
	for(int i = 1 ; i < n ; i++){
		//end 시간이 먼저 인것부터 top됨
		 int s = times[i].s, e = times[i].e;
		 int now = q.top();
		 
		 if(now>s){//겹치는경우 
		 	q.push(e);
		 }
		 else{
		 	q.pop();
			q.push(e);	
		 }	
	}
	cout<<q.size();
	 
	
}

 

 

참고

강의실배정

우선순위큐