백준 1931 회의실배정 C/C++

회의실 배정 실패

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

142120

44362

31412

29.544%

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 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

#include <iostream>

using namespace std;


typedef struct room
{
	int start;
	int end;
}Room;


void MergeTwoArea(Room arr[], int left, int mid, int right)
{
	int fIdx = left;
	int rIdx = mid + 1;
	int i;

	Room* sortArr = (Room*)malloc(sizeof(Room) * (right + 1));
	int sIdx = left;

	while (fIdx <= mid && rIdx <= right)
	{
		if (arr[fIdx].end <= arr[rIdx].end)
			sortArr[sIdx] = arr[fIdx++];
		else
			sortArr[sIdx] = arr[rIdx++];

		sIdx++;
	}

	if (fIdx > mid)
	{
		for (i = rIdx; i <= right; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}
	else
	{
		for (i = fIdx; i <= mid; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}

	for (i = left; i <= right; i++)
		arr[i] = sortArr[i];

	free(sortArr);
}

void MergeSort(Room arr[], int left, int right)
{
	int mid;

	if (left < right)
	{
		// 중간 지점을 계산한다.
		mid = (left + right) / 2;

		// 둘로 나눠서 각각을 정렬한다.
		MergeSort(arr, left, mid);
		MergeSort(arr, mid + 1, right);

		// 정렬된 두 배열을 병합한다.
		MergeTwoArea(arr, left, mid, right);
	}
}

int main(void)
{
	int n,now,cnt=1;
	cin >> n;
	Room* arr =new Room[n];
	
	for (int i = 0; i < n; i++)
		cin >> arr[i].start >> arr[i].end;

	MergeSort(arr, 0, n - 1);
	now = arr[0].end;


	for(int i=1;i<n;i++)
	{
		if (now <= arr[i].start)
		{
			cnt++;
			now = arr[i].end;
			
		}
	}
	printf("%d", cnt);

	return 0;
}

 

자꾸 실패한다고 뜬다.

 

어디가 틀린지 모르겠다.

 

나의 한계인가

 

답은 잘나오는데 백준이 자꾸 틀렸다고 한다. 이럴거면 예시를 몇 개 더주지