[백준] 1931 회의실 배정 - Java

 

 

 

그리디 문제에는 정렬이 따라오는 경우가 많다.

 

정렬의 기준을 뭐로 설정할지가 매우 중요하다. 이 부분에 대해 고민해보자.

 

 

이 문제의 경우는 끝나는 시간을 오름차순으로 정렬하고, 같다면 시작 시간을 오름차순으로 정렬해야 한다.

 

 

import java.util.*;
import java.io.*;
import java.math.*;

public class Main {			
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));						

		int N = Integer.parseInt(br.readLine());

		Time[] arr = new Time[N];

		for(int i=0; i<N; i++){
			StringTokenizer st = new StringTokenizer(br.readLine());

			int start = Integer.parseInt(st.nextToken());
			int fin = Integer.parseInt(st.nextToken());			

			arr[i] = new Time(start, fin);
		}

		Arrays.sort(arr);

		// for(int i=0; i<N; i++){
		// 	System.out.println(arr[i].start + " " + arr[i].fin);
		// }

		int cnt = 1;
		int f_time = arr[0].fin;

		for(int i=1; i<N; i++){
			if(f_time <= arr[i].start){
				cnt++;
				f_time = arr[i].fin;
			}		
		}

		System.out.println(cnt);


	}
}

class Time implements Comparable<Time>{
	int start, fin;

	Time(int a, int b){
		start = a;
		fin = b;
	}

	public int compareTo(Time o2){
		if(fin > o2.fin){
			return 1;
		}else if(fin == o2.fin){
			if(start > o2.start){
				return 1;
			}else{
				return -1;
			}
		}else{
			return -1;
		}
			
		
	}
}