DP-회의실 배정

 

 

이번에도 이중 배열의 정렬의 문제였다. 저번 문제와 동일하게 이번에는 끝나는 시간을 기준으로 정렬을 한후 바로바로 스케줄링 할 수 있게 처리해서 문제를 해결했다. 아래 그림을 참고하면 이해가 편할 것이다.

 

 

 

 

 

 

 

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

public class java {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int arr[][] = new int[sc.nextInt()][2];
        for(int i=0;i<arr.length;i++){
            for (int j = 0; j < 2; j++) {
                arr[i][j]=sc.nextInt();
            }
        }
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1]==o2[1])return o1[0]-o2[0];
                else return o1[1]-o2[1];
            }
        });

        int min = arr[0][1];
        int count =1;
        for (int i = 1; i < arr.length; i++) {
            if(arr[i][0]>=min){
                min=arr[i][1];
                count++;
            }
        }
        System.out.println(count);

    }
}

 

 

 

끝나는 시간을 봤을 때 짧은 것을 반복했을 때 해답이 나오게 된다.