[c++] 백준 1931번 - 회의실배정

# 백준1931번 URL

1931번: 회의실배정

 

 

위 예제는 그리디 알고리즘의 대표적인 문제이다. O(n^2)의 시간복잡도로 구하게 될 시 시간초과가 일어나므로

 

C++ STL에 속한 algorithm 라이브러리의 sort 함수를 사용하여 끝나는 시간이 빠른 순서대로 정렬을 해서 구하면 된다.

 

단, 끝나는 시간이 같을 경우 시작 시간이 빠른 순서로 정렬을 해야 하는 것에 주의한다.

 

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

using namespace std;

int result_count = 0;

typedef struct {
	int s;
	int e;
}info;

bool compare(info a, info b) {
	if (a.e == b.e) {
		return a.s < b.s;
	}

	return a.e < b.e;	
}

int main() {
	int num, max = 0;
	int s, e = 0;

	scanf("%d", &num);
	vector<info> v;

	for (int i = 0; i < num; i++) {
		scanf("%d %d", &s, &e);
		v.push_back({ s, e });
	}

	sort(v.begin(), v.end(), compare);
	int last =0 ;
	
	for (int i = 0; i < num; i++) {
		int comp_s = v[i].s;
		int comp_e = v[i].e;
		
		if (comp_s < last)
			continue;


		result_count++;
		last = comp_e;
	}

	printf("%d", result_count);
}