백준 1931 회의실 배정

그리디 알고리즘 문제로, 1개의 회의실에 최대 몇 개의 회의를 배정할 수 있는지 찾는 문제이다.

그리디 알고리즘으로 풀어야한다는 것만 생각할 수 있으면 쉽게 풀 수 있는 문제다.

 

우선, 회의가 끝나는 순서대로 회의를 지정한다.

첫 번째 회의부터 배정을 하고 첫 회의의 끝나는 시간을 기록한다.

그 다음 종료되는 회의의 시작 시간과 이전 회의의 끝나는 시간을 비교하여 이전 회의의 끝나는 시간보다 시작 시간이 큰 경우만 추가하고, 끝나는 시간을 갱신하고 배정 카운트를 끝낸다. 이렇게 모든 회의를 끝까지 조회해보고 최종 카운트된 숫자를 출력해주면 된다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <stdlib.h>
#include <string.h>

typedef struct room {
	int start, end;
} ROOM;

int compare(const void* a, const void* b) {
	ROOM info1 = *(ROOM*)a;
	ROOM info2 = *(ROOM*)b;

	if (info1.end == info2.end) {
		return (info1.start > info2.start ? 1 : (info1.start == info2.start ? 0 : -1));
	}
	else {
		return (info1.end > info2.end ? 1 : -1);
	}
}

int main() {
	int N;
	scanf("%d", &N);

	ROOM* nArr = (ROOM*)malloc(sizeof(ROOM) * N);
	memset(nArr, 0, sizeof(ROOM) * N);

	for (int i = 0; i < N; ++i) {
		scanf("%d %d", &nArr[i].start, &nArr[i].end);
	}

	qsort(nArr, N, sizeof(nArr[0]), compare); // 회의가 끝나는 순서대로 정렬

	int cnt = 0;
	int last_end_time = 0;

	for (int i = 0; i < N; ++i) {
		if (i == 0) {
			cnt++;
			last_end_time = nArr[i].end;
		}
		else if (last_end_time <= nArr[i].start) {
			cnt++;
			last_end_time = nArr[i].end;
		}
	}

	printf("%d\n", cnt);

	free(nArr);

	return 0;
}