קאָנטראָלירן צי צוויי ינטערוואַלז אָוווערלאַפּ צווישן אַ באַשטימט גאַנג פון ינטערוואַלז


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַמאַזאָן אַרסעסיאַם סיסקאָ דירעקטי דזשפּ מאָרגאַן מייקראָסאָפֿט קוואַלקאַם יאַנדעקס
דינאַמיש פּראָגראַממינג סאָרטינג

פּראָבלעם סטאַטעמענט

די פּראָבלעם "קוק אויב צוויי ינטערוואַלז אָוווערלאַפּ צווישן אַ באַשטימט גאַנג פון ינטערוואַלז" זאגט אַז איר האָט עטלעכע ינטערוואַלז. יעדער מעהאַלעך באשטייט פון צוויי וואַלועס, איינער איז סטאַרטינג צייט און די אנדערע ענדס צייט. די פּראָבלעם ויסזאָגונג פרעגט צו קאָנטראָלירן אויב ינטערוואַלז אָוווערלאַפּ יעדער אנדערע אויב אָוווערלאַפּס דרוקן 'יאָ' אַנדערש דרוקן 'ניין'.

בייַשפּיל

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 און דאַן קער אמת.
  7. צוריק פאַלש.

דערקלערונג

אונדזער פּראָבלעם איז צו קאָנטראָלירן צי צוויי ינטערוואַלז אָוווערלאַפּ צווישן אַ באַשטימט גאַנג פון ינטערוואַלז. אַזוי, מיר באַקומען אַ גאַנג פון ינטערוואַלז, יעדער מעהאַלעך באשטייט פון צוויי וואַלועס, איינער איז סאָף ווערט און די אנדערע איז סטאַרטינג ווערט פון אַ צייט מעהאַלעך. מיר מוזן באַשליסן אויב די ינטערוואַלז זענען אָוווערלאַפּינג. אויב קיין ינטערוואַלז זענען אָוווערלאַפּינג אָדער קאַווערינג די גאנצע מעהאַלעך, מיר מוזן דרוקן יאָ, אַנדערש דרוקן קיין. צוליב דעם, מיר וועלן געפֿינען זיך די מאַקסימום עלעמענט פון דער צייט ינטערוואַל ווייַל די סאָף צייט איז שטענדיק מאַקסימום, אַזוי מיר וועלן זוכן פֿאַר די מאַקסימום עלעמענט אין דער סאָף צייט מעהאַלעך.

נאָך דעם שאַפֿן אַ טעמפּ מענגע מיט די זעלבע גרייס ווי די געגעבן מענגע ווערט. ניצן דעם מענגע צו שטעלן די אָנהייב און ענדיקן צייט פון די מעהאַלעך. ביז אַהער, מיר וועלן באַקומען די וואַלועס פון סטאַרטינג צייט און ענדיקן צייט פון די מעהאַלעך. שטעלן די סטאַרטינג צייט און די ענדיקן צייט פון די מעהאַלעך אין די טעמפּ און ינקריסינג די סטאַרטינג צייט ווערט 1 און פאַרקלענערן די ווערט פון (סאָף צייט + 1) מיט 1 און דערהייַנטיקן די טעמפּ מענגע.

מיר וועלן דורכגיין די טעמפּ מענגע מיר באשאפן און דערהייַנטיקן אַרויף צו די מאַקסימום עלעמענט מיר געפֿונען אין די אָנהייב פון די קאָד. נאָך דעם וואָס מיר וועלן טאָן די קראַנט ווערט און די פֿריִערדיקע ווערט פון די טעמפּ מענגע, פֿאַר יעדער דורכקוק קאָנטראָל אויב איינער פון די דערהייַנטיקט ווערט האט די ווערט גרעסער ווי 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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (maxIntervalEndingTime + n) ווו “N” איז די נומער פון עלעמענטן אין די מענגע. ערשטער, מיר געפֿינען די מאַקסימום ינטערוואַלז וואָס מיר האָבן קאָס אָ (N) צייט. און דער שאַפונג פון פּרעפיקס מענגע ריקווייערז אָ (maxIntervalEndingTime).

ספעיס קאַמפּלעקסיטי

אָ (maxIntervalEndingTime) ווייַל מיר האָבן סטאָרד אַ מענגע פֿאַר דערגייונג ווי פילע ינטערוואַלז זענען אָוווערלאַפּינג אין אַ באַזונדער צייט.