문제 요약

[1931] 회의실 배정

• 그리디 대표 문제로 task scheduling problem으로 불림
• 회의 시작-끝나는 시간이 주어질 때 최대한 사용할 수 있는 회의의 최대 개수를 출력하는 문제
• 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있음 (ex. 1시 ~ 3시 회의 -> 바로 이어서 3시 ~ 4시 회의 진행 가능)

풀이 과정

처음 문제를 풀 때는 회의시간이 가장 짧은 회의를 우선적으로 택하면 되지 않을까? 라고 생각하여 짧은 회의 순으로 (시간차가 같은 경우에는 시작 시간이 빠른 회의를 먼저) 정렬하고 손으로 풀어보았으나 틀렸음.

구글의 도움을 빌려 문제 푸는 방법을 알게 됨.

1. 회의가 빨리 끝나는 순으로 진행
2. 끝나는 시간이 같은 경우에는 먼저 빨리 시작하는 회의를 택

즉 시작 시간과 끝나는 시간이 입력되면 끝나는 시간을 오름차순으로 정렬 후, 끝나는 시간 값이 같다면 시작 시간 순으로 오름차순 정렬한다.

코드 (C/C++)

1. 시작 시간과 끝나는 시간에 대한 정보를 저장하는 구조체 timeTable 선언
2. C언어의 stdlib.h에서 제공하는 정렬함수인 qsort 사용
   • qsort(정렬할 배열의 포인터, 배열의 총 수, 배열 원소 하나 크기, 비교함수)

비교함수

• 1, 0, -1 중에 하나를 반환
• 오름차순으로 정렬한다면 (내림차순인 경우 등호 바꿔서)
  * 첫번째 변수 > 두번째 변수 => 1
  • 첫번째 변수 < 두번째 변수 => -1
  • 첫번째 변수 = 두번째 변수 => 0

//언어 cpp, 메모리 2680KB, 시간 44ms
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct timeTable
{
	int start;
	int end;
}timeTable;

int compare(const void* a, const void* b) //비교함수 (오름차순)
{
	timeTable A = *(timeTable*)a;
	timeTable B = *(timeTable*)b;
    //첫번째 변수의 끝시간 > 두번째 변수의 끝시간인 경우 -> 1을 반환해야 오름차순 정렬됨
	if (A.end > B.end) return 1;
	else if (A.end == B.end) //끝나는 시간이 같다면 
	{
    	//시작 시간을 오름차순 정렬
		if (A.start > B.start) return 1; 
		else return -1;
	}
	else return -1; 
}

int main(void)
{
	int n;
	int cnt = 1;
	int start;
	int end;
	scanf("%d", &n); //회의실의 수
	timeTable* arr;
	arr = (timeTable*)malloc(sizeof(timeTable) * n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d %d", &arr[i].start, &arr[i].end);
	}
	qsort(arr, n, sizeof(timeTable), compare);
	start = arr[0].start;
	end = arr[0].end;
	for (int i = 1; i < n; i++)
	{
		if (arr[i].start < end) continue;
		start = arr[i].start;
		end = arr[i].end;
		cnt += 1;
	}
	printf("%d\n", cnt);
}

알아가는 점

처음에는 2차원 배열을 정렬하려고 했는데 구조체로 선언할 수 있다는 점을 공부하면서 알게 됨. 비교 함수 작성 방법, cpp의 pair를 사용하면 더 간단