[백준][JAVA]회의실배정(1931번) - 그리디 알고리즘

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

1931번: 회의실 배정

* 문제는 해당 게시물 참고바랍니다.

 

그리디 알고리즘이란

그리디 알고리즘은 흔히 탐욕 알고리즘이라고도 불리며 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법입니다. 각 단계에서 한 선택이 최선의 선택을 한 것이길 바라고 전체적으로도 최선이길 바라는 알고리즘입니다.

 

해당 문제를 해결한 코드입니다.

  

    
    
    
    
  
import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int [][]table = new int[n][2];

        int count =0;

        //입력받기
        for(int i=0; i<n; i++){
            for(int j=0; j<2; j++){
                table[i][j] = scanner.nextInt();
            }
        }

        //정렬
        Arrays.sort(table, new Comparator<int[]>() {
            @Override
            public int compare(int[] table1, int[] table2) {

                // 종료시간이 같을 경우 시작시간이 빠른순으로 정렬
                if(table1[1] == table2[1]) {
                    return table1[0] - table2[0];
                }
                return table1[1] - table2[1];
            }
        });


        //counting
        int j=0;
        for(int i=0; i<n-1; i++){
            int tmp = table[j][1];
            if(tmp <= table[i+1][0]){
                count++;
                j=i+1;
            }
        }

        System.out.println(count+1);
    }
}

이렇게 해결하였습니다.

 

여기서 

  

    
    
    
    
  
System.out.println(count+1);

해당 코드에서 count+1을 한 이유는 최초의 선택을 배정 가능한 테이블의 수로 포함하기 위해서 입니다.

 

결과