논리 설명: 회의 스케줄러 - Leetcode [Java] using Two Pointers

설명

두 사람의 가용성 시간 슬롯 배열 slots1 및 slots2와 회의 기간이 주어지면 두 사람 모두에게 작동하고 지속 시간이 있는 가장 빠른 시간 슬롯을 반환합니다.

요구 사항을 충족하는 공통 시간 슬롯이 없으면 빈 배열을 반환합니다.

예 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의 열린 슬롯)을 찾아 회의 시간이 주어졌을 때 회의를 할 수 있도록 해야 합니다.

논리

동료 A의 가용 슬롯을 보고 동료 B의 가용 슬롯과 비교합니다.

사용 가능한 슬롯 범위가 회의 시간 내에 없는 경우 동료의 사용 가능한 다음 슬롯을 찾습니다.

질문: 다른 동료의 현재 사용 가능한 슬롯과 비교하기 위해 먼저 어떤 동료의 사용 가능한 슬롯을 살펴봐야 합니까?

대답: 현재 사용 가능한 슬롯에 대한 다른 동료의 종료 시간과 비교하여 현재 사용 가능한 슬롯에 대한 종료 시간이 더 낮은 동료는 다음 사용 가능한 슬롯을 확인해야 합니다.

알고리즘: 투 포인터 기법

루프에서 두 개의 포인터를 사용합니다.

단 하나의 루프로 O(n3) 또는 O(n2)에서 O(n)까지의 시간 복잡도를 줄이는 데 도움이 됩니다.

의사 코드

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

인덱스 0에서 두 개의 포인터를 초기화합니다.

slots1의 길이에 대한 포인터는 slots1의 길이보다 작고 slots2의 길이에 대한 포인터는 slots2의 길이보다 작습니다.
ㅏ. 각 동료에 대한 현재 슬롯을 보유하도록 두 어레이를 초기화/재초기화합니다.
비. 두 정수 초기화/재초기화: 1) 두 동료의 현재 사용 가능한 슬롯 사이의 최대 시작 시간을 저장합니다. 2) 두 동료의 현재 사용 가능한 슬롯 사이의 최소 종료 시간을 저장합니다.
씨. 기간이 최대 시작 시간과 최소 종료 시간 범위 내에 있으면 시작 시간과 시작 시간 + 기간을 반환합니다.
동료 A의 종료 시간이 동료 B의 종료 시간보다 짧으면 동료 A의 포인터를 증가시킵니다.
동료 B의 종료 시간이 동료 A의 종료 시간보다 짧으면 동료 B의 포인터를 증가시킵니다.
그렇지 않으면 동료 A와 B의 포인터를 모두 증가시킵니다.

빈 배열을 반환합니다. 겹치는 슬롯이 없어 동료들이 주어진 회의 시간 동안 회의를 가질 수 있습니다.

시나리오

시나리오 1: 동료 A의 종료 시간과 동료 B의 시작 시간이 겹칩니다.

그러나 겹침은 회의 시간을 커버하기에 충분하지 않습니다.



시나리오 2: 동료 B의 종료 시간과 동료 A의 시작 시간이 겹칩니다.

그러나 겹침은 회의 시간을 커버하기에 충분하지 않습니다.



시나리오 3: 동료 B의 종료 시간이 동료 A의 시작 시간과 겹칩니다(또는 그 반대).

그리고 중복은 회의 시간을 커버하기에 충분합니다.

암호

class Solution {
    public List<Integer> 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<>();
    }
}