백준 1931 회의실 배정

처음 생각했을때 큐를 사용해서 모든 경우의 수를 탐색하는 방법을 사용했다. 하지만 이는 O(N^2)의 시간복잡도를 가지는데 최대 100000개의 회의가 생길수 있으니 100000^2=10000000000 즉 최악의 경우 100억번의 연산이라는 결과를 맞이하게 된다. 이는 2초안에 풀수 없음을 의미하기 때문에 시간초과라는 글을 본뒤 푸는 방법을 변경했어야 했다.

 

또 생각든 게 끝나는 시간의로 솔팅을 하게 된다면 해결이 가능하지 않을까였다. 끝나는 시간으로 솔팅을 하게 되면 

(1,100), (2,101), (101, 800), (800,3000) , (100,10000)이면 1이 100으로 100이 10000으로 가기 때문에 2번째부터 시작하는게 맞지 않나라는 고민이 들었다. 하지만 이는 의외로 간단하게 풀리는데 첫번째를 고르고 굳이 100이 아니라 100보다 큰 끝나는 시간이 빨리 끝나는 녀석을 고르면 되는 것이다. 

 

또한 구현에서도 prioriy_queue를 선택했는데 이 녀석에 처음 element들을 넣었을때 전부가 정렬이 되지 않아서 적잖게 당황했다. 이유는 priority_queue 자체는 원소가 들어오거나 빠질때 Heap sort algorithm을 수행한다. 그러므로 빼거나 넣는 횟수가 n번이라면 이는 nlogn의 시간복잡도를 가진다. 좀더 정확한 분석은 힙솔트를 공부하고 하겠다.

 

코드 :

 

#include 
#include 
#include 
using namespace std;

struct confer_info {
	int start_time;
	int end_time;
	confer_info(int start, int end) : start_time(start),end_time(end){}
};

class cmp {
public :
	bool operator()(confer_info s1, confer_info s2) {
		if (s1.end_time != s2.end_time) return s1.end_time > s2.end_time;
		else return s1.start_time > s2.start_time;
	}
};


int N, ans;
int start_time, end_time;
priority_queue<confer_info, vector, cmp> pq;

void Input() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d %d", &start_time, &end_time);
		pq.push(confer_info{ start_time, end_time });
	}
}

void Calc() {
	int max_time = 0;
	while (!pq.empty()) {
		int start_time = pq.top().start_time;
		int end_time = pq.top().end_time; pq.pop();
		if (max_time <= start_time) {
			max_time = end_time;
			ans++;
		}
	}
	printf("%d", ans);
}

void Solve() {
	Input();
	Calc();
}

int main(void) {
	Solve();
	return 0;
}