주어진 간격 세트에서 두 간격이 겹치는 지 확인하십시오.


난이도 중급
자주 묻는 질문 아마존 아르 세슘 시스코 지시 JP 모건 Microsoft 퀄컴 Yandex 주차
동적 프로그래밍 정렬

문제 정책

"주어진 간격 집합간에 두 간격이 겹치는 지 확인"문제는 몇 가지 간격 집합이 제공되었음을 나타냅니다. 각 간격은 두 값으로 구성됩니다. 하나는 시작 시간이고 다른 하나는 종료 시간입니다. 문제 설명은 겹치는 경우 간격이 서로 겹치는 지 확인하고 'YES'를 인쇄하고 그렇지 않으면 'NO'를 인쇄하도록 요청합니다.

arr[] = { { 2, 3 }, { 5, 6 }, { 1, 4 }, { 7, 9 }}
Yes

설명

왜냐하면 시간 간격 (2, 3)과 (1, 4)가 서로 겹치기 때문입니다.

주어진 간격 세트에서 두 간격이 겹치는 지 확인하십시오.

이미지는 간격 (2,3)과 (1,4)가 겹치는 것을 명확하게 보여줍니다.

arr[] = { { 1, 4 }, { 5, 6 }, { 7, 9 }, { 10, 13 } }
No

설명

간격이 서로 겹치지 않기 때문입니다.

암호알고리즘

  1. 간격 (최대 요소)의 최대 종료 값을 찾으십시오.
  2. 우리가 찾은 최대 요소와 동일한 크기의 배열을 만듭니다.
  3. 주어진 입력 배열을 탐색하고 각 간격의 시작 및 끝 값을 가져옵니다.
  4. 임시 배열에 삽입하고 시작 시간 값을 1 씩 늘리고 (종료 시간 + 1) 값을 1 줄입니다.
  5. 우리가 찾은 최대 요소까지 배열을 탐색합니다.
  6. 이전 값과 현재 값을 합산하여 임시 배열에 저장하고 1보다 큰 값이 있는지 확인한 다음 true를 반환합니다.
  7. 거짓을 반환합니다.

설명

우리의 문제는 주어진 간격 세트 사이에 두 개의 간격이 겹치는 지 확인하는 것입니다. 따라서 간격 세트가 주어지며 각 간격은 두 값으로 구성됩니다. 하나는 종료 값이고 다른 하나는 시간 간격의 시작 값입니다. 간격이 겹치는 지 확인해야합니다. 간격이 겹치거나 전체 간격을 포함하는 경우 yes를 인쇄하고 그렇지 않으면 no를 인쇄해야합니다. 이를 위해 우리는 종료 시간이 항상 최대이기 때문에 시간 간격의 최대 요소를 찾을 것입니다. 따라서 우리는 종료 시간 간격에서 최대 요소를 검색 할 것이며 항상 최대 값을 찾습니다.

이 후 임시 생성 정렬 주어진 배열 값과 동일한 크기를가집니다. 간격의 시작 및 종료 시간을 입력하려면이 배열을 사용하십시오. 그러나 그 전에 간격의 시작 시간과 종료 시간 값을 얻습니다. 간격의 시작 시간과 종료 시간을 temp에 넣고 시작 시간 값을 1 씩 증가시키고 (종료 시간 + 1) 값을 1 감소시키고 임시 배열을 업데이트합니다.

생성 한 임시 배열을 탐색하고 코드 시작 부분에서 찾은 최대 요소까지 업데이트합니다. 그런 다음 현재 값과 임시 배열의 이전 값을 추가 한 후 업데이트 된 값이 1보다 큰 값이 있는지 각 순회 검사에 대해 겹치는 부분이 있는지 확인합니다. true이면 true를 반환합니다. 모든 순회가 완료된 후 false를 반환합니다.이 줄에 오면 겹침이 발생하지 않음을 의미합니다. 따라서 우리는 거짓을 반환 할 것입니다. 살펴보고 싶다면 비슷한 문제가 있습니다. 겹치는 간격 병합.

암호

간격 겹침을 확인하는 C ++ 코드

#include <algorithm>
#include <iostream>

using namespace std;

struct Input_Interval
{
    int start;
    int end;
};

bool overLappingCheck(Input_Interval arr[], int n)
{

    int maximumElement = 0;

    for (int i = 0; i < n; i++)
    {
        if (maximumElement < arr[i].end)
            maximumElement = arr[i].end;
    }

    int temp[maximumElement + 2] = { 0 };

    for (int i = 0; i < n; i++)
    {
        int startingTime = arr[i].start;

        int endingTime = arr[i].end;
        temp[startingTime]++, temp[endingTime + 1]--;
    }

    for (int i = 1; i <= maximumElement; i++)
    {
        temp[i] += temp[i - 1];

        if (temp[i] > 1)
            return true;
    }

    return false;
}

int main()
{
    Input_Interval arr1[] = { { 2, 3 }, { 5, 6 }, { 1, 4 }, { 7, 9 } };
    int n1 = sizeof(arr1) / sizeof(arr1[0]);

    overLappingCheck(arr1, n1) ? cout << "Yes\n" : cout << "No\n";

    Input_Interval arr2[] = { { 1, 4 }, { 5, 6 }, { 7, 9 }, { 10, 13 } };
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    overLappingCheck(arr2, n2) ? cout << "Yes\n" : cout << "No\n";

    return 0;
}
Yes
No

간격 겹침을 확인하는 Java 코드

class IntervalOverLapping
{
    static class Input_Interval
    {
        int start;
        int end;
        public Input_Interval(int start, int end)
        {
            super();
            this.start = start;
            this.end = end;
        }
    };
    
    static boolean overLappingCheck(Input_Interval arr[], int n)
    {

        int maximumElement = 0;

        for (int i = 0; i < n; i++)
        {
            if (maximumElement < arr[i].end)
                maximumElement = arr[i].end;
        }
        
        int []temp = new int[maximumElement + 2];
        
        for (int i = 0; i < n; i++)
        {
            int startingTime = arr[i].start;

            int endingTime = arr[i].end;
            temp[startingTime]++;
            temp[endingTime+1]--;
        }
        
        for (int i = 1; i <= maximumElement; i++)
        {
            temp[i] += temp[i - 1];

            if (temp[i] > 1)
                return true;
        }
        
        return false;
    }
    
    public static void main(String[] args)
    {
        Input_Interval arr1[] = { new Input_Interval(2, 3), new Input_Interval(5, 6),
                           new Input_Interval(1, 4), new Input_Interval(7, 9)
        };
        int n1 = arr1.length;

        if(overLappingCheck(arr1, n1))
            System.out.print("Yes\n");
        else
            System.out.print("No\n");

        Input_Interval arr2[] = { new Input_Interval(1, 4), new Input_Interval(5, 6),
                           new Input_Interval(7, 9), new Input_Interval(10, 13)
        };

        int n2 = arr2.length;
        if(overLappingCheck(arr2, n2))
            System.out.print("Yes\n");
        else
            System.out.print("No\n");
    }
}
Yes
No

복잡성 분석

시간 복잡성

O (maxIntervalEndingTime + n) 어디에 "엔" 배열의 요소 수입니다. 첫째, 우리는 O (N) 시간이 소요되는 최대 Interval을 찾습니다. 그리고 접두사 배열을 만들려면 O (maxIntervalEndingTime)가 필요합니다.

공간 복잡성

O (maxIntervalEndingTime) 특정 시간에 겹치는 간격을 찾기 위해 배열을 저장했기 때문입니다.