Объясненная логика: Планировщик собраний – Leetcode [Java], использующий приоритетную очередь

Описание

Задан массив времени встречи интервалы где интервалы[i] = [начало _i , конец _i ] , возвращает минимальное требуемое количество конференц-залов.

Пример 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

Сценарий

Сегодня ваши коллеги из разных команд предоставили вам список времени начала и окончания собраний. Создание новых комнат для собрания – это сложная задача, поэтому вы хотели бы повторно использовать комнаты , которые были освобождены предыдущей встречей. Вам поручено выяснить сколько комнат будет использоваться.

Логика

1. Изначально ни одна комната не занята, поэтому мы вводим первое самое раннее время начала.

2. Для последующих совещаний проверьте, освобождены ли существующие помещения, если да, используйте их повторно. Если нет, то откройте новую комнату.

Структура данных: Приоритетная очередь

• head приоритетной очереди – это наименьший элемент, основанный на естественном упорядочении или упорядочении на основе компаратора. Когда мы опрашиваем очередь, она возвращает объект head из очереди.

Псевдокод

1. Отсортируйте массив интервалы в порядке возрастания времени начала. Используйте Arrays.sort() с Comparator во 2-м параметре .

2. Создайте приоритетную очередь. Мы будем использовать это для хранения времени окончания каждого интервала. Используйте Приоритетную очередь структуру данных. Почему Приоритетная Очередь? Чтобы убедиться, что когда мы проверяем начало очереди, мы видим самое раннее время окончания в начале очереди. Это позволяет эффективно проверить, можем ли мы повторно использовать комнату.

3. Добавьте время окончания первого отсортированного интервального массива.

4. Выполните итерацию по интервальному массиву, начиная с индекса 1. a. Проверьте, есть ли время начала в i-м интервальном массиве равно или больше времени окончания в начале очереди | queue.peek() , затем удалите время окончания в начале очереди queue.poll() . б. Добавьте время окончания i-го отсортированного интервального массива. очередь.предложение() . Примечание: в приоритетной очереди мы вставляем новый элемент в индекс очереди на основе естественного порядка . Возвращает размер очереди.

Сценарии

Сценарий 1: самое раннее время окончания в очереди НЕ больше или равно времени начала нового собрания.

Сценарий 2: самое раннее время окончания в очереди больше или равно времени начала нового собрания.

Код

Решение из имени пользователя leetcode: титасдатта93

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) (o1, o2) -> (o1[0] - o2[0])
        );

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

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

        for(int i=1; i= 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();
    }
}

Оригинал: “https://dev.to/clarkngo/logic-explained-meeting-room-ii-leetcode-java-1gh5”