백준 회의실 배정

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

아 첨에 dfs로 풀었는데 시간 초과가 발생해서 

흠 그리드 알고리즘을 참고하니 훨씬 간단하게 풀었습니다.

어렵네요.

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

using namespace std;

struct Meeting {
	int start;
	int end;
};

bool compare(const Meeting& a, const Meeting& b) {
	if (a.end == b.end) {
		return a.start < b.start;
	}
	return a.end < b.end; // 종료 시간을 기준으로 정렬
}

int main() {
	int N; // 회의의 개수
	cin >> N;

	vector<Meeting> meetings(N); // 회의 정보를 저장할 벡터

	for (int i = 0; i < N; i++) {
		cin >> meetings[i].start >> meetings[i].end;
	}

	// 회의를 종료 시간을 기준으로 정렬
	sort(meetings.begin(), meetings.end(), compare);

	int max_count = 1; // 최소한 첫 번째 회의는 가능하므로 1로 초기화
	int end_time = meetings[0].end; // 첫 번째 회의의 종료 시간을 기준으로 설정

	for (int i = 1; i < N; i++) {
		if (meetings[i].start >= end_time) {
			// 현재 회의의 시작 시간이 이전 회의의 종료 시간보다 크거나 같으면
			// 회의실을 사용할 수 있으므로 개수를 증가시키고 종료 시간을 갱신
			max_count++;
			end_time = meetings[i].end;
		}
	}

	cout << max_count << endl;

	return 0;
}