논리 설명: 회의 스케줄러 - 우선 순위 대기열을 사용하는 Leetcode [Java]

설명

intervals i intervals[i] = [start i , end인 회의 시간 배열 ]이 주어지면 필요한 최소 회의실 수를 반환합니다.

예 1

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

예 2

Input: intervals = [[7,10],[2,4]]
Output: 1

예 3:

Input: intervals = [[0,30],[5,10],[10,15],[15,20],[30,50],[30,70]]
Output: 2

대본

오늘, 다른 팀의 동료가 회의 시작 시간과 회의 종료 시간 목록을 제공했습니다. 회의를 위해 새 회의실을 설정하는 것은 번거롭기 때문에 이전 회의에서 확보한 회의실을 다시 사용하고 싶을 것입니다. 당신은 얼마나 많은 방이 사용될 것인지 알아내야 합니다.

논리

처음에는 사용 중인 방이 없으므로 첫 번째 가장 빠른 시작 시간을 삽입합니다.

후속 회의의 경우 기존 회의실이 비어 있는지 확인하고, 그렇다면 회의실을 다시 사용하십시오. 그렇지 않은 경우 새 방을 엽니다.

데이터 구조: 우선순위 큐

우선 순위 대기열의 헤드는 자연 순서 또는 비교기 기반 순서를 기반으로 하는 최소 요소입니다. 큐를 폴링하면 큐에서 헤드 개체를 반환합니다.

의사 코드

intervals 배열을 시작 시간의 오름차순으로 정렬합니다. 두 번째 매개변수에서 Comparator와 함께 Arrays.sort()를 사용하십시오.

우선순위 대기열을 만듭니다. 이것을 사용하여 각 간격의 종료 시간을 저장합니다. PriorityQueue 데이터 구조를 사용합니다. 왜 우선순위 큐인가? 대기열의 헤드를 확인할 때 대기열의 헤드에서 가장 빠른 종료 시간을 확인할 수 있습니다. 이렇게 하면 방을 재사용할 수 있는지 확인하는 것이 효율적입니다.

첫 번째 정렬된 간격 배열의 끝 시간을 추가합니다.

인덱스 1에서 시작하여 간격 배열을 반복합니다.
ㅏ. i번째 간격 배열의 시작 시간이 대기열 헤드의 종료 시간queue.peek()보다 크거나 같은지 확인한 다음 대기열 헤드의 종료 시간queue.poll()을 제거합니다.
비. i번째 정렬된 간격 배열의 종료 시간을 추가합니다. queue.offer() . 참고: 우선 순위 대기열에서는 자연 순서에 따라 대기열 인덱스에 새 요소를 삽입합니다.

대기열의 크기를 반환합니다.

시나리오

시나리오 1: 대기열에서 가장 빠른 종료 시간은 새 회의 시작 시간보다 크거나 같지 않습니다.




시나리오 2: 대기열에서 가장 빠른 종료 시간이 새 회의 시작 시간보다 크거나 같습니다.

암호

Solution leetcode에서 사용자 이름: titasdatta93

Time Complexity: O(nlogn) Space Complexity: O(n)

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        //First sort the intervals in asc. order of starting time

        //TC: Of the below step : O(nlogn)
        Arrays.sort(
            intervals, 
            (Comparator<int[]>) (o1, o2) -> (o1[0] - o2[0])
        );

        //Create priority queue to store ending times of each interval
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        //Add the ending time of first sorted interval
        queue.offer(intervals[0][1]);

        for(int i=1; i<intervals.length; i++) {
            if(intervals[i][0] >= queue.peek()) {
                queue.poll(); //Poll from min heap happens in O(n) time
            }

            queue.offer(intervals[i][1]);
        }     //hence total time complexity here is O(logn) 

        return queue.size();
    }
}