Рубрики
Без рубрики

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

задача кодирования – два указателя. С тегами java, coding, leetcode, алгоритмы.

Описание

Учитывая доступность временных интервалов массивов слотов 1

Если нет общего временного интервала, удовлетворяющего требованиям, верните пустой массив.

Пример 1

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
Output: [60,68]

Пример 2

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 12
Output: []

Сценарий

Сегодня двум вашим коллегам необходимо встретиться в течение определенного периода времени в самое раннее доступное время. Оба они дали вам список открытых слотов в свое время. Вам поручено найти перекрывающиеся слоты (открытый слот коллеги A и сотрудник с открытым слотом B ), который позволил бы им провести встречу с учетом продолжительности встречи.

Логика

  1. Посмотрите на коллегу A доступный слот И сравните его с коллегой B доступным слотом.

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

Вопрос: На какой следующий доступный слот сотрудника мы должны посмотреть в первую очередь, чтобы сравнить с текущим доступным слотом другого сотрудника?

Ответ: Сотрудник, у которого время окончания текущего доступного слота меньше, чем у другого сотрудника, для его текущего доступного слота, – это тот, кого мы должны проверить на наличие следующего доступного слота.

Алгоритм: Техника с двумя указателями

  • Использование двух указателей в цикле.
  • Помогает уменьшить временную сложность O(n 3 ) или O(n 2 ) до (n) всего одним циклом.

Псевдокод

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

  2. Инициализируйте два указателя с индексом 0.

  3. В то время как указатель на длину слотов 1 меньше длины слотов 1 , а указатель на длину слотов 2 меньше длины слотов2 . а. Инициализируйте/повторно инициализируйте два массива, чтобы сохранить текущий слот для каждого сотрудника. б. Инициализируйте/повторно инициализируйте два целых числа: 1) для сохранения максимального времени запуска между двумя текущими доступными слотами сотрудника. 2) для сохранения минимального времени окончания между двумя текущими доступными слотами сотрудника. c. Если длительность находится в диапазоне максимального времени начала и времени окончания шахты, то верните время начала и время начала + продолжительность. Ещё если время окончания работы сотрудника A меньше времени окончания сотрудника B , затем увеличьте сотрудника Указатель/|. Ещё если время окончания работы сотрудника B меньше, чем время окончания работы сотрудника A , затем увеличьте указатель коллеги B . Else увеличить обоих сотрудников A и указатели B . Возвращает пустой массив.

  4. Отсутствие перекрывающихся интервалов позволило бы сотрудникам провести встречу, учитывая продолжительность встречи .

Сценарии

Сценарий 1: время окончания работы сотрудника В качестве времени окончания совпадает со временем начала работы сотрудника B.

ОДНАКО перекрытия НЕДОСТАТОЧНО для покрытия продолжительности совещания.

Сценарий 2: время окончания времени окончания сотрудника B совпадает с временем начала сотрудника.

ОДНАКО перекрытия НЕДОСТАТОЧНО для покрытия продолжительности совещания.

Сценарий 3: время окончания времени окончания сотрудника B совпадает с временем начала сотрудника (или наоборот).

И перекрытия достаточно, чтобы покрыть продолжительность собрания.

Код

class Solution {
    public List minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
        Arrays.sort(slots1, (a,b)-> a[0]-b[0]);
        Arrays.sort(slots2, (a,b)-> a[0]-b[0]);

        int p1 = 0;
        int p2 = 0;

        while (p1 < slots1.length && p2 < slots2.length) {
            int[] curr1 = slots1[p1];
            int[] curr2 = slots2[p2];

            int start = Math.max(curr1[0], curr2[0]);
            int end = Math.min(curr1[1], curr2[1]);

            if (end - start >= duration) 
                return Arrays.asList(start,start+duration);
            else if (curr1[1] < curr2[1]) p1++;
            else if (curr2[1] < curr1[1]) p2++;
            else {
                p1++;
                p2++;
            }

        }
        return new ArrayList<>();
    }
}

Оригинал: “https://dev.to/clarkngo/logic-explained-meeting-scheduler-leetcode-java-using-two-pointers-4881”