[C언어] 백준 1931 : 회의실 배정

생각의 흐름

이번에는 입력값이 오름차순이라는 조건이 없다. 그래서 qsort를 사용해야겠다고 생각했다.
정렬의 기준이 필요한데, 먼저 왼쪽에 있는 값(1, 3, 0 ...)을 x라고 두고, 오른쪽에 있는 값(4, 5, 6 ...)을 y라고 생각했다. 먼저 그리디에 의해 y값이 제일 작은것을 고를 것이다. 따라서 y값을 기준으로 오름차순으로 정렬하고, y값이 같은 경우가 생기면 x값을 오름차순으로 정렬했다.

그러면 위 예제처럼 정렬이 되는데, 일단 1,4는 확정이다. 그 다음에 고를 수는 5,7이고, 그 다음은 8, 11이다. 직전 y값보다 현재 x값이 크거나 같아야 되는 규칙을 찾을 수 있다.
여기까지 생각하고 코드를 작성했다.

내가 푼 코드

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

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

int compare(const void *a, const void *b)
{
	greed A = *(greed *)a;
	greed B = *(greed *)b;
	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()
{
	greed arr[100010];
	int i, j, n, count;
	scanf("%d", &n);
	i = 0;
	while (i < n)
	{
		scanf("%d %d", &arr[i].x ,&arr[i].y);
		i++;
	}
	qsort(arr, n, sizeof(greed), compare);
    // 여기까지 정렬하는 부분
	i = 1;
	j = 0;
	count = 1; // 1,4는 확정이기에 1부터 시작
	while (i < n)
	{
		if (arr[j].y <= arr[i].x) // 임의로 j잡아주고
		{
			j = i; // 조건에 만족하면 i값으로 업데이트
			count++; // 갯수 세줌
		}
		i++;
	}
	printf("%d", count);
}

다른 사람들도 구조체 선언해서 진행했다. 뿌듯하다.