글 읽기 - 회의실배정(그리디 알고리즘) 문제 질문입니다.

boffin 6년 전 0

제 접근 방법이 틀린건가요 ㅜ

어느 부분에서 반례가 있는지 모르겠습니다 도와주세요!

#include<stdio.h>
/*-----------------------------
1. 우선 각 회의들의 종료시간을 비교하여 오름차순으로 정렬합니다.
2. 정렬된 0번 배열을 시작으로 이전 회의(befo)의 종료시간과 그 이후의 종료시간이
   제일 짧은 회의의 시작시간을 비교하여 서로 시간이 겹치지 않으면 cnt++을 해줍니다.
3. cnt를 출력합니다.

*/
typedef struct meeting {
	int start;
	int end;
}meeting;

/*구조체의 end 값을 오름차순으로 퀵정렬 시킨다*/
int compare(void *first, void *second);



int main() {
	int n;
	meeting meet[100001] = { 0 };
	int cnt = 1;
	int befo = 0;

	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &meet[i].start, &meet[i].end);
	}



	//printf("\n\n");
	qsort(meet, n, sizeof(meeting), compare);

	//for (int i = 0; i < n; i++)printf("%d %d\n", meet[i].start,meet[i].end);

	for (int i = 1; i <n; i++) {
		if (meet[befo].end <= meet[i].start) {
			cnt++;
			befo = i;
		}
	}

	printf("%d", cnt);
}



int compare(void *first, void *second) {
	meeting* finishf = (meeting*)first;
	meeting* finishs = (meeting*)second;

	if (finishf->end > finishs->end) return 1;
	else if (finishf->end < finishs->end) return -1;
	else 0;
}

chogahui05 6년 전 1

(1) 종료시간을 증가 순으로 정렬하셨다..

(2) 종료 시간이 같다면 시작 시간이 큰 순으로 정렬하셨다..

왠만하면 맞으실텐데...

일단 이상해 보이는 건 55번째 줄이네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

회의실배정(그리디 알고리즘) 문제 질문입니다.

boffin 6년 전 0

chogahui05 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말