[C] 백준 1931번 회의실 배정

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

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력 1

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력 1

4

아이디어 스케치

핵심은 "각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자" 이다.
위의 핵심을 구현하기 위해 회의가 끝나는 시간을 1순위로 오름차순 정렬하고, 회의가 끝나는 시간이 같을 때는 회의가 시작하는 시간을 2순위로 오름차순 정렬을 하면 될 것 이다.
매 반복마다 숫자 2개를 입력 받기 때문에 구조체를 만든 후 구조체 배열을 이용하면 수월하게 구현이 가능할 것 이다.

코드 분할 설명

typedef struct {
	int x;
	int y;
}time;

매 반복마다 숫자 2개씩 입력받아 같은 배열 인덱스에 저장하기 위해 구조체를 설정

int compare(const void* first, const void* second)
{
	time a = *(time*)first;
	time b = *(time*)second;

	if (a.y > b.y)
		return 1;
	else if (a.y == b.y) {
		if (a.x > b.x)
			return 1;	//a와 b 스왑
		else
			return -1;
	}
	else
		return -1;

}

y값 즉 회의가 끝나는 시간을 기준으로 오름차순을 정렬하고, y의 값이 같을 때는 회의가 시작하는 시간(x)값을 기준으로 오름차순 정렬을 함

qsort(arr, n, sizeof(time), compare);

빠른 정렬을 위해 퀵정렬을 이용

a = arr[0].y;
	for (int i = 1; i < n; i++) {
		if (a <= arr[i].x){
			a = arr[i].y;
			count++;
		}
	}

a값에 첫 회의의 끝나는 시간(y)을 저장
끝나는 시간(y)과 같거나 더 늦게 시작하는 회의(arr[i])를 찾을 경우 찾은 회의의 끝나는 시간(y)를 a에 저장한 후 갯수 카운팅

배열을 y값을 기준으로 오름차순 후 y값이 같을 때 x값을 기준으로 오름차순 정렬을 했기 때문에 배열을 앞에서부터 순서대로 조건을 걸어 count값을 구해도 올바르게 나옴

전체코드

#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int x;
	int y;
}time;

int compare(const void* first, const void* second)
{
	time a = *(time*)first;
	time b = *(time*)second;

	if (a.y > b.y)
		return 1;
	else if (a.y == b.y) {
		if (a.x > b.x)
			return 1;
		else
			return -1;
	}
	else
		return -1;

}

int main()
{
	time arr[100000];
	int n;
	int count = 1;
	int a;


	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d %d", &arr[i].x, &arr[i].y);
	}
	qsort(arr, n, sizeof(time), compare);

	a = arr[0].y;
	for (int i = 1; i < n; i++) {
		if (a <= arr[i].x){
			a = arr[i].y;
			count++;
		}
	}

	printf("%d", count);

	return 0;

}

실행 결과