백준 1931번

https://www.acmicpc.net/problem/1931

1931번: 회의실배정

문제 풀이

그리디 알고리즘의 문제로서 어떤 부분을 우선순위 설정해야할지가 중요하다. 이 문제는 최대 많이 사용 할수 있는 회의 수를 출력하는 것이므로 회의 종료시간을 우선순위로 두고, 회의가 가장 먼저 끝나는것부터 먼저 한다면 최대 사용 가능한 회의수가 출력 될것이다.

따라서 회의 종료시간을 오름차순으로 정렬하고 회의 종료시간이후 다음 회의 시작 시간이 가장 가까운 회의를 실행한다면 될 것입니다.

 

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

public class BOJ1931 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
        int[][] time = new int[N][2];
        
        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<2; j++) {
                time[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
       
        Arrays.sort(time, new Comparator<int[]>() {
            @Override
            public int compare(int[] arg0, int[] arg1) {
                if(arg0[1] == arg1[1]) {
                    return arg0[0] - arg1[0];
                } else {
                    return arg0[1] - arg1[1];
                }
            }
        });    
        
        int end = -1;
        int count = 0;
        
      
        for(int i=0; i<N; i++) {
            if(time[i][0] >= end ) {
                end = time[i][1];
                count++;
            }
        }
        
        System.out.println(count);
    }
 
}