दिलेल्या अंतराच्या सेटमध्ये दोन अंतराने ओव्हरलॅप झाल्याचे तपासा


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन आर्सेसियम सिस्को डायरेक्टि जेपी मॉर्गन मायक्रोसॉफ्ट Qualcomm यांडेक्स
डायनॅमिक प्रोग्रामिंग वर्गीकरण

समस्या विधान

“दिलेल्या अंतराच्या सेटमध्ये दोन अंतराल ओलांडले आहेत का ते तपासा” ही समस्या सांगते की आपल्याला काही अंतराळे दिले आहेत. प्रत्येक मध्यांतरात दोन मूल्ये असतात, एक वेळ प्रारंभ होत आहे आणि दुसरे वेळ संपत आहे. प्रॉब्लेम स्टेटमेंट मधे एखादी अंतराल आच्छादित असेल की नाही हे तपासण्यास सांगेल, तर 'होय' प्रिंट करा 'नाही' प्रिंट करा.

उदाहरण

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

स्पष्टीकरण

कारण, वेळ मध्यांतर (2, 3) आणि (1, 4) एकमेकांशी ओव्हरलॅप होतात.

दिलेल्या अंतराच्या सेटमध्ये दोन अंतराने ओव्हरलॅप झाल्याचे तपासा

प्रतिमेमध्ये अंतर (२,)) आणि (१,2,3) आच्छादित स्पष्टपणे दर्शविले गेले आहे.

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 पेक्षा जास्त आहे का ते तपासून ते आच्छादित करेल की हे आच्छादित आहे का ते खरे, नंतर सत्य परत. सर्व ट्रॅव्हर्सिंग पूर्ण झाल्यानंतर, खोटे परत करा, जर आपण या ओळीत येथे आलो तर अर्थ ओव्हरलॅपिंग होत नाही. तर आपण चुकीचे परत येऊ. आपण पाहू इच्छित असल्यास, अशीच एक समस्या आहे जी आम्हाला विचारते आच्छादित मध्यांतर विलीन करा.

कोड

मध्यांतर ओव्हरलॅपिंग तपासण्यासाठी सी ++ कोड

#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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (मॅक्सइंटरव्हलइंडिंगटाइम + एन) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. प्रथम, आम्हाला जास्तीत जास्त मध्यांतर ओ (एन) वेळ खर्च करावा लागतो. आणि मग उपसर्ग अ‍ॅरे तयार करण्यासाठी ओ (मॅक्सइंटरव्हॅलिंग टाइम) आवश्यक आहे.

स्पेस कॉम्प्लेक्सिटी

ओ (मॅक्सइंटरव्हलएंडिंग टाइम) कारण एका विशिष्ट वेळी किती अंतराने आच्छादित होत आहेत हे शोधण्यासाठी आम्ही अ‍ॅरे संचयित करत आहोत.