[ 백준 ] [ 자바 ][ 1931 ] 회의실 배정

이 문제는 코드는 간단하나 

 

그 원리가 제일 중요한데

 

원리에서 도출되는 정렬순서, 방법 ( comparator ) 주 쟁점인듯 하다 .

 

그리디 알고리즘에서는 정당성을 고려하는데 이 부분에 대해서 공부가 필요할듯 싶다 ( 귀류법 ) 

package back;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

class Bis{
	int start;
	int end;
	Bis(int start, int end){
		this.start = start;
		this.end = end;
	}
}
public class backjoon_Main_1931_회의실배정 {
	static int N;
	static ArrayList arr = new ArrayList();
	public static void main(String[] args) throws IOException {
		
		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	        
	        N = Integer.parseInt(br.readLine());
	        for(int i = 0; i < N; i++) {
	            StringTokenizer st = new StringTokenizer(br.readLine()," ");
	             int start = Integer.parseInt(st.nextToken());
	             int end = Integer.parseInt(st.nextToken());
	             arr.add(new Bis(start, end));
	        }		
	        
	        /*
	         *  양수가 리턴되면  현재 오브젝트가 앞
	         *  음수가 리턴되면 현재 오브젝트가 뒤
	         *  0이 리턴되면 동일 값 간주 입력순서
	         */
	        Collections.sort(arr, new Comparator() {
	            public int compare(Bis c1, Bis c2) {
	                if (c1.end > c2.end) { //큰놈이 앞
	                    return 1;
	                } else if (c1.end < c2.end) { //작으면 뒤로 
	                    return -1;
	                }
	                //시작 
	                else {
	                	if(c1.start > c2.start) {
	                		return 1;
	                	}else if(c1.start < c2.start){
	                		return -1;
	                	}else {
	                		return 0;
	                	}
	                }
	            }
	        });
//	        
//	         for(int i = 0; i < arr.size(); i++) {
//	        	 System.out.println(arr.get(i).start +  " "+ (arr.get(i).end)) ;
//	         }
	         solve();
	}
	public static void solve() {
		int idx = 0;
		int count = 1;
		for(int i = 1; i < arr.size(); i++) {
			int currentEnd = arr.get(idx).end;
			if ( arr.get(i).start < currentEnd) {
				continue;
			}
			count +=1;
			idx = i;
		}
		System.out.println(count);
	}
}