글 읽기 - [java] 틀린이유 , 반례를 못찾겠습니다

chlcc 4년 전 0

안녕하세요.

저는 priorityqueue로 최소힙구현해서 문제에 접근했습니다.

반례 부탁드립니다. ㅜㅜ

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] arg) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		
		PriorityQueue<long[]> pq = new PriorityQueue<>(new Comparator<long[]>() {
			@Override
			public int compare(long[] o1, long[] o2) {
				
				if(o1[0] != o2[0]) {
					return Long.compare(o1[0], o2[0]);
				}else {
					return Long.compare(o1[1], o2[1]);
				}
				
			}
		});
		
		long[] arr;
		int cnt = 0;
		
		for (int i = 0; i < n; i++) {
			arr = new long[2];
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 2; j++) {
				arr[j] = Long.parseLong(st.nextToken());
			}
			pq.add(arr);
		}

		long[] pivot;
		
		while (!pq.isEmpty()) {
			pivot = pq.poll();
			
			while (!pq.isEmpty()) {

				if(pq.peek()[0] >= pivot[1]) {
					cnt ++;
					break;
				}
				
				if(pq.peek()[1] - pq.peek()[0] < pivot[1] - pivot[0]) {
					break;
				}
				pq.poll();
			}
		}
		System.out.println(++cnt);
	}
	
}

ha_ram 4년 전 1

이 문제는 남은 회의중에서 가장 빨리 시작하는 회의를 배정해서 푸는게 아니라 남은 회의중에서 가장 빨리 끝나는 회의를 배정해아 하는 문제입니다. 이 부분을 잘 생각하시고 구현하시면 될 것 같습니다.

chlcc 4년 전 1

헝 .. 이제확인했네요 감사합니다 다시 풀어볼께요

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

문제

문제

출처

ICPC

[java] 틀린이유 , 반례를 못찾겠습니다

chlcc 4년 전 0

ha_ram 4년 전 1

chlcc 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말