[그리디 알고리즘] 회의실배정

예제 입력 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

 

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

1931번: 회의실배정

- 정답은 회의가 일찍 끝나는 시간 기준으로 그리디 알고리즘으로 풀 수 있다.

- 회의 끝나는 시간으로 정렬하여 순서대로 처리하여 풀 수 있는데, 주의할 점은 회의가 끝나는 시간이 같을 경우 회의가 일찍 시작하는 순으로 정렬하여야 한다. 회의 시작시간과 끝시간이 같은 경우를 처리하여야 하기 때문인데, 이를 구현하지 않으면 아래 케이스를 풀 수 없다.

 

1 1

1 2  <- 이 회의가 끝나버리면 현재 시간이 2가 되어 바로 아래 회의를 진행할 수 없다.

1 1

2 2

2 3

#include <stdio.h>

const int MAX_COUNT = 100000;

class meeting
{
public:
	unsigned int start;
	unsigned int end;

	meeting() { start = end = 0; }
	meeting(unsigned int start, unsigned int end) : start(start), end(end) {}

	bool operator<=(meeting other)
	{
		if (end == other.end) return start <= other.start;
		else return end <= other.end;
	}
};

int N;
meeting timeTable[MAX_COUNT];
meeting tempTimeTable[MAX_COUNT];

void mergeSort(int start, int end)
{
	if (start >= end) return;
	int mid = (start + end) / 2;

	mergeSort(start, mid);
	mergeSort(mid + 1, end);

	int i = start;
	int j = mid + 1;
	int k = 0;

	while (i <= mid && j <= end)
	{
		if (timeTable[i] <= timeTable[j])
		{
			tempTimeTable[k++] = timeTable[i];
			i++;
		}
		else
		{
			tempTimeTable[k++] = timeTable[j];
			j++;
		}
	}

	while (i <= mid)
	{
		tempTimeTable[k++] = timeTable[i];
		i++;
	}

	while (j <= end)
	{
		tempTimeTable[k++] = timeTable[j];
		j++;
	}

	for (int i = start; i <= end; i++)
	{
		timeTable[i] = tempTimeTable[i - start];
	}
}



int main(void)
{
	unsigned int now = 0;
	int result = 0;

	scanf("%d", &N);

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

	mergeSort(0, N - 1);

	for (int i = 0; i < N; i++)
	{
		if (now <= timeTable[i].start)
		{
			now = timeTable[i].end;
			result++;
		}
	}

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

	return 0;
}