백준 1931 그리디 알고리즘

백준 1931

 

우선 저는 처음에 시작시간이 가장 빠르고 시작 시간이 같다면 회의시간이 짧은 순서대로 정렬을 했습니다.

근데 그렇게 하니 계속 답이 이상하게 나와서... 곰곰히 생각을 했는데 종료시간이 빠른 순서대로 정렬을 해야하는게 맞더라구요.

그래서 그렇게 정렬을 하고 마지막 종료시간과 같거나 큰 회의시간이 있으면 res를 플러스 1 해주었습니다.

 

다음은 제 코드입니다.

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

public class B1931 {
	private static int N;
	private static Integer value[][];
	private static int res = 0;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		value = new Integer[N][2];
		for(int i = 0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			value[i][0] = Integer.parseInt(st.nextToken());
			value[i][1] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(value, new Comparator<Integer[]>(){
			@Override
			public int compare(Integer[] o1, Integer[] o2) {
				if(o1[1] == o2[1]) {
					return o1[0] - o2[0];
				}else {
					return o1[1] - o2[1];
				}
			}
		});

		int last_end_time = 0;
		for(int i = 0; i<N; i++) {
			if(value[i][0] >= last_end_time) {
				res++;
				last_end_time = value[i][1];
			}
		}
		System.out.println(res);

	}
}

ㄷ  !