1931번 : 회의실

www.acmicpc.net/problem/1931

1931번: 회의실배정

 

keypoint

하루에 최대로 열 수 있는 회의의 수를 구해야 하기 때문에 회의의 종료시간에 초점을 맞추어야 한다. 회의가 빨리 끝난다면 다음 회의를 열 수 있기 때문이다. 따라서 회의가 끝나는 시간을 기준으로 오름차순 정렬을 해야한다. 후에 회의가 끝나는 시간에 맞춰 다음 회의 시작시간이 가까운 회의부터 실행을 하면 답이 나온다.

 

import java.util.*;

public class Main {
	public static void main(String[] args) {
 		Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();					//총 회의의 개수 입력
        int [][]arr = new int [N][2];			//각 회의의 시작시간과 종료시간을 넣을 2차원 배열 생성
        
        for(int i = 0; i<N; i++) {
        	arr[i][0] = sc.nextInt();			//각 회의의 시작시간과 종료시간을 입력
            arr[i][1] = sc.nextInt();
            }
            
        Arrays.sort(arr,new Comparator<int[]>() {	//회의시간을 정렬
        	@Override
            public int compare(int[] arg0, int[] arg1) {
            	if(arg0[1] == arg1[1]) {			//회의의 종료시간이 같다면
                	return Integer.compare(arg0[0],arg1[0]);	//회의의 시작시간을 오름차순으로 정렬한다.
                    }
                    return Integer.cimpare(arg0[1],arg1[1]);	//회의의 종료시간을 오름차순으로 정렬한다.
    			}
             }
    
    	int time = 0; //임시로 다음 회의가 시작할 수 있는 시간을 담는 변수
        int count = 0;	//하루에 최대로 열 수 있는 회의의 수
        
        for(int i = 0; i<N; i++) {
        	if(arr[i][0] >= time) {	//이전 회의의 종료시간보다 해당 회의의 시작시간이 같거나 이후일 경우
            	count++;
                time = arr[i][1]; // 회의의 종료시간을 time 변수에 담아준다.
            }
        }
    	sc.close();
        System.out.println(count);
    
    }
}