Проверете дали има два интервали што се преклопуваат меѓу дадениот сет на интервали


Ниво на тешкотија Медиум
Често прашувано во Амазон Арцесиум Cisco Директи ЈП Морган Мајкрософт Квалком Yandex
Динамичко програмирање Сортирање

Изјава за проблем

Проблемот „Проверете дали има преклопување на два интервали во даден сет на интервали“, вели дека ви се дадени некои групи интервали. Секој интервал се состои од две вредности, едната е време на започнување, а другата е време на завршување. Изјавата за проблемот бара да се провери дали некој од интервалите се преклопува едни со други ако се преклопуваат, потоа отпечатете „ДА“ на друго место отпечатете „НЕ“.

пример

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. Вметнете во низата temp и зголемете ја вредноста на времето на започнување за 1 и намалете ја вредноста на (времето на завршување + 1) за 1.
  5. Поминете ја низата до максималниот елемент што го најдовме,
  6. Сумирајте ја претходната вредност и тековната вредност и зачувајте ги во низата temp, проверете дали некоја вредност е поголема од 1, а потоа вратете ја точно.
  7. Врати неточно.

Објаснување

Нашиот проблем е да провериме дали има два интервали што се преклопуваат меѓу дадениот сет на интервали. Значи, ни се дава збир на интервали, секој интервал се состои од две вредности, едната е крајна вредност, а другата е почетна вредност на временски интервал. Треба да утврдиме дали некој од интервалите се преклопува. Ако некој од интервалите се преклопува или го покрива целиот интервал, тогаш мора да отпечатиме да, инаку да отпечатиме не. За ова, ќе го дознаеме максималниот елемент на временскиот интервал, бидејќи времето на завршување е секогаш максимално, така што ќе го бараме максималниот елемент во временскиот интервал на завршувањето, секогаш ја наоѓаме максималната вредност таму.

По ова создадете темпиран низа кои имаат иста големина како и на дадената вредност на низата. Користете ја оваа низа за да го поставите времето на започнување и завршување на интервалот. Но, пред тоа, ќе ги добиеме вредностите на времето на започнување и времето на завршување на интервалот. Внесете го времето на започнување и времето на завршување на интервалот во темпо и зголемувајќи ја вредноста на времето на започнување за 1 и намалете ја вредноста на (време на завршување + 1) за 1 и ажурирајте ја низата на темпо.

Toе ја пресечеме низата temp што ја создадовме и ќе ажурираме до максималниот елемент што го најдовме на почетокот на кодот. Потоа, откако ќе направиме додавање на моменталната вредност и претходната вредност на низата temp, за секоја проверка на пресекот дали некоја од ажурираната вредност има вредност поголема од 1, ова ќе провери дали се појави некое од преклопувањата, дали е точно, тогаш вратете се точно. Откако ќе заврши целата траверзација, вратете неточно, ако дојдеме тука во оваа линија, значи дека нема преклопување. Значи, ќе се вратиме лажни. Ако сакате да погледнете, има сличен проблем што го бара од нас спојуваат интервали што се преклопуваат.

Код

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

Јава код за да се провери преклопувањето на интервалот

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) каде „Н“ е бројот на елементи во низата. Прво, го наоѓаме максималниот интервал што нè чини О (N) време. И тогаш за создавање на низата префикси е потребно O (maxIntervalEndingTime).

Комплексноста на просторот

О (maxIntervalEndingTime) затоа што зачувавме низа за да откриеме колку интервали се преклопуваат во одредено време.