Java 프로그래머스 호텔 대실

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

프로그래머스

문제 분류 : 코딩테스트 연습 > 연습문제 > 호텔 대실 

난이도 : 2

 

문제 접근

그리디 + 정렬 문제이다.

1. 우선순위 큐(pq1)에 시작이 빠른 순서대로 정렬한다.

2. 우선순위 큐(pq2)는 호텔이다. 이 우선순위 큐는 빨리 끝나는 순서로 정렬되어 있다.

    만약 호텔에서 가장 빨리 끝나는 대실 시간 보다 pq1(손님)의 시작 시간이 더 빠르면 우선 순위 큐(pq2)에        추가 한다. 

    추가 하면 우선순위 큐(pq2)의 크기를 max 와 비교해서 갱신한다.

3. max가 손님들이 최소한으로 사용한 객실의 수

정답 코드 

import java.util.*;

class Solution {
    
    static class hotel{
        int start; int end;
        public hotel(int start, int end){
            this.start = start;
            this.end   = end;
        }
    }
    public int solution(String[][] book_time) {
        PriorityQueue<hotel> pq1 = new PriorityQueue<>((o1, o2)->o1.start-o2.start);
        for(int i = 0; i < book_time.length; i++){
            String st = book_time[i][0];
            String et = book_time[i][1];
            pq1.add(new hotel(calculate(st), calculate(et)));
        }
        int max = 0;
        PriorityQueue<hotel> pq2 = new PriorityQueue<>((o1, o2)->o1.end-o2.end);
        while(!pq1.isEmpty()){
            if(pq2.isEmpty()){
                pq2.add(pq1.poll());
                max = Math.max(max, 1);
                continue;
            }
            hotel hotel = pq1.poll();
            if(pq2.peek().end + 10 <= hotel.start){
                pq2.poll();
                pq2.add(hotel);
            }
            else{
                pq2.add(hotel);
            }
             max = Math.max(max, pq2.size());
        }
        return max;
    }
    public static int calculate(String input){
        String [] split = input.split(":");
        int hour = Integer.parseInt(split[0]);
        int min  = Integer.parseInt(split[1]);
        
        return (hour * 60) + min;
    }
}