.leetcode(253. Meeting Rooms II)

문제

https://leetcode.com/problems/meeting-rooms-ii/

문제 해설

시간대를 겹치지 해서 회의실을 잡는데 회의실을 최소로 빌려서 해결해라.

문제 풀기 전

1. 한 10분동안은 문제를 오해했다. 첫번째는 그냥 가장 작은 수인줄, 두번째는 작은 수의 갯수인줄 오해했다.
2. 결국 이건 꼬리물기식으로 문제를 풀어야하는데 예전에 한번 풀었떤 문제와 비슷하다는 생각이 들었다.

직접 푼 풀이

소요시간: 29분(09:50 ~ 10:19)

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        //정렬
        Arrays.sort(intervals, Comparator.comparing(each -> each[0]));

        List<Integer> ends = new ArrayList<>();
        //비교
        for (int i=0; i<intervals.length; i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];

            int targetIndex = -1;
            for (int j=0; j<ends.size(); j++) {
                if (start >= ends.get(j)) {
                    targetIndex = j;
                    break;
                }
            }

            if (targetIndex != -1) {
                ends.set(targetIndex, end);
            } else {
                ends.add(end);
            }
        }


        return ends.size();
    }
}

느낀점

1. 그래 "763. Partition Labels"와 같은 원리로 풀었다. 뒷부분을 기억해두고 그걸 이어 붙여나가는 것이다.
2. 먼저 시작 시간순으로 정렬을 하고 이어 붙여 나가되, 기존 회의실 모두에서 겹치면 새로 회의실을 만든다. 만약 겹치지 않는 기존 회의실이 있다면 기존 회의실 끝나는 시간과 새로 이었다.
3. 여튼 시작시간순을 Arrays.sort(intervals, Comparator.comparing(each -> each[0]));를 이용해서 구현하였고 그 뒤는 기존 회의실의 마지막 값을 기억해둠으로써 이어나가게 구성하였다.
4. 이걸 PriorityQueue로도 풀 수 있다. 결국 제일 일찍 끝난걸 맨 위로 정렬하되, 저장된 회의끝나는 시간과 새로 시작할 시간을 비교해서 겹치면 하나 더 하고 안 겹치면 빼주고 새로 끝나는 시간 넣어주는 방식이다.
5. 이외에도 포인터를 이용해서 풀 수도 있다. 시작시간과 종료시간을 분리한다. 시작시간, 종료시간을 순서대로 정렬하고, 시작시간이 종료시간을 넘어가는 순간 이정까지 써왔던 방들에서 하나를 빼주면 되므로 아래와 같이 로직을 꾸며 볼 수 있다.

솔루션 공부 후 추가로 푼 풀이

# PriorityQueue를 이용한 풀이
class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }

        Arrays.sort(intervals, Comparator.comparing(each -> each[0]));


        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> a - b);
        pq.add(intervals[0][1]);

        for (int i=1; i<intervals.length; i++) {
            if (intervals[i][0] >= pq.peek()) {
                pq.poll();
            }


            pq.add(intervals[i][1]);
        }


        return pq.size();
    }
}

# pointer를 이용한 풀이
class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int[] starts = new int[intervals.length];
        int[] ends = new int[intervals.length];

        for (int i=0; i<intervals.length; i++) {
            starts[i] = intervals[i][0];
            ends[i] = intervals[i][1];
        }

        Arrays.sort(starts);
        Arrays.sort(ends);

        int startPointer=0;
        int endPointer=0;
        int usedRooms = 0;

        while(startPointer < intervals.length) {
            if (starts[startPointer] >= ends[endPointer]) {
                usedRooms--;
                endPointer++;
            }

            startPointer++;
            usedRooms++;
        }

        return usedRooms;
    }
}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)