[JAVA] 프로그래머스 : 호텔 대실

https://school.programmers.co.kr/learn/courses/30/lessons/155651#

처음에는 최대한 많은 회의 시간을 배정하는 greedy 문제와 같이 '퇴실 시간'을 기준으로 정렬했었다. 하지만, 이것은 특정 시간 이후에 시작되는 작업을 먼저 고려하는 문제이기 때문에 '시작 시간'을 기준으로 정렬해야 한다.

시작 시간 기준 정렬

• 여러 회의가 있고 각 회의의 시작 시간에 따라 회의를 정렬하여 일정을 계획
• 특정 시간 이후에 시작되는 작업을 먼저 고려
• 작업이나 이벤트의 흐름을 '시간순'으로 정리하며, '시작 시점'을 기준으로 작업을 처리하거나 배치할 때 유용

종료 시간 기준 정렬

• 회의가 끝난 후 다음 회의를 시작할 수 있는 시간을 고려하는 경우
• 일정을 빈틈없이 계획하는 경우
• 작업이 종료된 후 사용할 수 있는 자원을 관리하는 경우
• 작업이 빨리 끝난 후 다음 작업을 원할하게 배치하는 경우에 유용

import java.util.*;

class Solution {
    public int solution(String[][] book_time) { //예약 시간이 문자열 형태로 담김
        //종료시간에 10을 더하기
        //[][0] : 시작시간
        //[][1] : 종료시간
        //end값과 start값을 비교해서 현재 end값 뒤에 다음 start가 가능하면 end값을 새 end값으로 변경
        //안되면 새로운 end값을 넣기
        int[][] time = new int[book_time.length][2];
        
        for(int i=0; i<book_time.length; i++){
            int start = Integer.parseInt(book_time[i][0].replace(":","")); //시작시간
            int end = Integer.parseInt(book_time[i][1].replace(":","")); //종료시간
            end = end + 10; //끝나는 시간 + 10

            if(end % 100 >= 60){
                end = end + 40;
            }
            
            time[i][0] = start;
            time[i][1] = end;            
        }
        
        Arrays.sort(time, new Comparator<int[]>(){
            //시작 시간을 기준으로 오름차순 정렬
            @Override
            public int compare(int[] o1, int[] o2){
                return o1[0] - o2[0];
            }
        });
        
        //이미 정렬되어 있는 것들을 넣기 -> 우선순위큐 : 가장 작은 요소가 우선순위를 가져서 먼저 배치됨
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i=0; i<time.length; i++){
            int startT = time[i][0];
            int endT = time[i][1];
            
            //큐가 비어있으면 add
            if(!queue.isEmpty() && queue.peek() <= startT){ //큐의 가장 작은 값이 시작 시간보다 작으면
                queue.poll(); //맨 앞 요소 제거
            }
            queue.offer(endT);
        }
        return queue.size();
    }
}