[PS] Meeting Rooms(Medium) solution in JAVA

Meeting Rooms2 문제

회의시간이 주어지면 총 사용해야하는 회의실이 최소 몇개인가를 구하는 문제이다.

Easy 만큼 쉬운줄알고 정렬하고 그냥 막 풀었다가 아차 싶었다.

 

처음에 접근한 방법은 Map 에 모든 시간 데이터를 넣고 겹치는 시간을 넣은 List 의 사이즈를 비교하는방법이었는데 아니 무슨 미팅룸 시간이라면서 10만자리 대의 숫자를 input 으로 주길래 시간초과로 실패했다. 리트코드의 단점이 아닐까 input 의 사이즈가 명시되지 않는 문제들이 있는것

 

PQ 를 쓰면 시간내에 들어올 수 있다.

 

코드를 보여주고 그림으로 설명하겠다.

public Interval[] convert(int[][] arr) {
    return Arrays.stream(arr)
            .map(it -> new Interval(it[0], it[1]))
            .toArray(Interval[]::new);
}


public int minMeetingRooms(int[][] intervals) {
    Interval[] arr = convert(intervals);
    if (arr.length == 0) {
        return 0;
    }

    Arrays.sort(
            arr,
            Comparator.comparingInt(Interval::getS));

    PriorityQueue<Integer> pq =
            new PriorityQueue<>(
                    arr.length,
                    Comparator.comparingInt(a -> a));

    pq.add(arr[0].getE());

    for (int i = 1; i < arr.length; i++) {
        if (arr[i].getS() >= pq.peek()) {
            pq.poll();
        }
        pq.add(arr[i].getE());
    }

    return pq.size();
}

 

풀이의 핵심은 시작시간으로 정렬을 해 두었기 때문에

회의실을 점유(pq내부에있음) 하고 있었는데 그보다 큰 시작시간이 들어오면 회의실을 비워주면(pq.poll) 되는 것이다. 회의실을 비워주고 그대신 다시 점유할 것을 pq에 add 해준다 물론 가장 빨리 끝나는 회의실보다 시작해되는 회의실이 작으면 새로 회의실을 할당해주는 것이다. 

공통적으로 회의실 할당 pq.add 를 해주고 시간이 끝난 것은 poll 해주시면 회의실의 개수가 유지된다.

 

결과적으로 pq 의 size 를 return 해주면 원하는 값이 되게 된다.

 

끝!