글 읽기 - 회의실 배정 문제 오랫동안 고민 했는데 잘 안되네요...ㅜ

hj_d 7년 전 0

처음에는 시작 시간 순으로 정렬 하고 DP 로 했는데 안되더라구요 그래서

끝나는 시간 순으로 정렬을 하고 끝나는 시간 짧은 순으로 추가해 갔는데 그러면 최대의 경우를 구할수 있다고 생각 했는데..

방식이 틀렸나요? 아니면 코드에서 실수가 있나요?ㅜㅜ

#include<stdio.h>
#include<algorithm>
using namespace std;
struct time {
	int s, e;
};
bool Com(time a,time b)
{
	return a.e < b.e;
}
int main()
{
	int N,i;
	time g[100001];
	scanf("%d", &N);
	for (i = 0; i < N; i++)
		scanf("%d %d", &g[i].s, &g[i].e);
	sort(g, g+N, Com);
	int ans = 1, end = g[0].e;
	for (i = 1; i < N; i++)
	{
		if (end <= g[i].s)
		{
			ans++;
			end = g[i].e;
		}
	}
	printf("%d\n", ans);
}

alohajihwan 7년 전 2

6
1 3
3 100
4 5
6 6
5 6
7 7

입력일 때 5가 나와야 하는 데 4가 나오네요...

끝나는 시간이 같은 두 회의에 대해 정리를 해줘야 할 거 같습니다. 위 코드로는 5 6 혹은 6 6 둘중 하나가 if문에 의해 없어진거 같습니다.

hj_d 7년 전 0

아 감사합니다

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

문제

문제

출처

ICPC

회의실 배정 문제 오랫동안 고민 했는데 잘 안되네요...ㅜ

hj_d 7년 전 0

alohajihwan 7년 전 2

hj_d 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말