글 읽기 - 1931번 회의실 배정(자바) 반례를 찾습니다 ㅠ

qhsl1213 3년 전 0

제 아이디어를 소개합니다.

1. 회의 정렬

회의 시작 시간을 기준으로 오름차순정렬.

만약 회의 시작 시간이 같다면 회의 종료 시간을 기준으로 오름차순정렬.

즉,

1 1

1 3

2 2

2 4

2 7

5 6

5 6

6 7

이렇게 정렬.

2. 회의 선택 준거

회의는 1개 이상이므로, 일단 정렬된 회의 목록의 첫 번째 회의는 무조건 일정에 추가된다.

그 후 다음 동작을 수행

while(남은 회의가 있을 경우)

if(다음 회의의 시작 시간 >= 마지막으로 선택된 회의의 종료시간)

다음 회의를 일정에 추가

else

if(다음 회의의 총 진행 시간 < 마지막으로 선택된 회의의 총 진행 시간)

마지막으로 선택된 회의를 일정에서 빼고, 대신에 다음 회의를 일정에 추가

이 문제에 대한 질문이 질문 게시판에 꽤 많길래, 반례로 제시된 꽤 많은 테스트 데이터들과 결과를 비교해봤지만 오답을 발견하지 못했습니다..

아이디어 자체가 잘못된 것일까요?

package GridyAgorithm;
import java.io.*;
import java.util.*;

public class Conference {
	static PriorityQueue<Confer>pq = new PriorityQueue<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		for(int i=0; i<N; i++) {
			String[] confer = br.readLine().split(" ");
			pq.add(new Confer(Long.parseLong(confer[0]), Long.parseLong(confer[1])));
		}
		
		
		// 일단 한 개의 회의는 반드시 가능하므로(N >= 1).
		Confer ing = pq.poll();
		int total = 1;
		
        // 회의 선택 준거
		while(!pq.isEmpty()) {
			Confer cmp = pq.poll();
			if(cmp.start >= ing.end) {
				ing = cmp;
				total++;
			}else {
				if(cmp.end - cmp.start < ing.end - ing.start) ing = cmp;
			}
		}
		System.out.println(total);
	}
}

// 회의실 객체
class Confer implements Comparable<Confer>{
	long start;
	long end;
	
	public Confer(long start, long end) {
		super();
		this.start = start;
		this.end = end;
	}
    
    // 정렬 기준
	@Override
	public int compareTo(Confer o) {
		if(this.start > o.start) {
			return 1;
		}else if(this.start == o.start){
			if(this.end >= o.end)
				return 1;
			else
				return -1;
		}else
			return -1;
	}
}

qhsl1213 3년 전 0

현재 질문 게시판을 더 돌다가 반례를 발견했습니다.

3
0 1000
998 1002
1001 2000

answer = 2

output = 1

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