글 읽기 - 고수님들 회의실 배정 질문이 있습니다.

adamdoha 3년 전 0

끝나는 시각을 기준으로 정렬했고, 만약 끝나는 시각이 같다면 회의 시간이 짧은 순으로 정렬했을 때 97%에서 틀리게 되는데, 이 코드에 대한 반례가 무엇인가요?

왜 회의 시간이 시작된 순으로 탐색을 해야만 정답인 것인지 궁금합니다.

어차피 답에 영향을 미치는 것은 회의 시간이 끝나는 시각 아닌가요? 그중에서 회의 시간이 가장 짧은 순으로 먼저 배정하는 것이 더 Greedy한 것 아닌가요?

첨부하는 코드는 97%에서 틀리게 됩니다.

회의가 끝나는 시간의 오름차순으로, 회의가 시작되는 시간의 내림차순으로 정렬한 코드입니다.

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n=Integer.parseInt(br.readLine());
        PriorityQueue<int[]> q=new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] o1,int[] o2) {
                if(o1[1]==o2[1]) return Integer.compare(o2[0],o1[0]);
                return Integer.compare(o1[1], o2[1]);
            }
        });
        for(int i=0;i<n;i++) {
            st=new StringTokenizer(br.readLine());
            int from=Integer.parseInt(st.nextToken());
            int to=Integer.parseInt(st.nextToken());
            q.add(new int[] {from,to});
        }
        int answer=0;
        int t=0;
        while(!q.isEmpty()) {
            int[] p=q.poll();
            if(p[0]>=t) {
                t=p[1];
                ++answer;
            }
        }
        System.out.println(answer);
    }
}

ghghgh777 3년 전 2

adamdoha 3년 전 0

아차차, 시작 시간과 끝나는 시간이 동일한 경우를 생각 못했네요.

답변 정말 감사합니다 :)

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

문제

문제

출처

ICPC

고수님들 회의실 배정 질문이 있습니다.

adamdoha 3년 전 0

ghghgh777 3년 전 2

adamdoha 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말