코드트리 [자바 java] 회의실 준비 구현

https://www.codetree.ai/missions/8/problems/implement-scheduling-meeting-room?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 회의가 시작하는 시간과 끝나는 시간들이 주어졌을 때, 하나의 회의실에서 열릴 수 있는 회의 수의 최댓값을 구하는 문제가 있다고 하자. 

 

이렇게 주어졌을 때, 그리디로 풀 수 있는 세가지 방법이 있다.

 

1. 시작시간을 기준으로 오름차순  --> 더 늦게 시작하지만 일찍 끝나는 회의가 간과된다.

2. 회의시간을 기준으로 오름차순 --> 시작시간과 끝나는 시간이 고려되지 않는다. 

3. 끝나는 시간을 기준으로 오름차순 --> 예외가 발생하지 않는다.

 

그래서 이차원 배열을 선언하고 이 속에 회의시작시간과 끝나는 시간을 넣은 다음, 끝나는 시간을 기준으로 오름차순한 다음 차례로 앞에서부터 채워간다.

 

 

이 방법이 가능한 이유는 k가 짧을수록 사용할 수 있는 회의시간이 길어지기 때문입니다.(k를 작은 것부터 하나씩 탐색함으로서 최대한 효율적으로 풀 수 있도록 하였다.)

 

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

public class Main {
    public static void main(String[] args) throws IOException{
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       int n = Integer.parseInt(br.readLine());

       StringTokenizer st;

       int[][] arr = new int[n][2];

       for(int i = 0;i<n;i++){
        st  = new StringTokenizer(br.readLine());
        arr[i][0] = Integer.parseInt(st.nextToken());
        arr[i][1] = Integer.parseInt(st.nextToken());
       }

       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 end = 0;
       int cnt = 0;

       for(int i = 0;i<n;i++){
        if(end <= arr[i][0]){
            end = arr[i][1];
            cnt++;
        }
       }

       System.out.println(cnt);

    }
}