چڪاس ڪريو ته ڇا ٻه وقفي وقف ٿيل ڏنل وقف جي وچ ۾ اوورلوپ ٿي ويندا آهن


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon آرڪسيميم Cisco سڌو JP مارگن Microsoft جي Qualcomm ياندڪس
متحرڪ پروگرامنگ ترتيب ڏيڻ

مسئلي جو بيان

مسئلو "چيڪ ڪريو جيڪڏهن ڪو ٻه وقفو وقف ٿيل سيٽ جي وچ ۾ ختم ٿي ويا آهن" بيان ڪري ٿو ته توهان کي ڪجهه وقفو ڏنو وڃي ٿو. هر وقفو ٻن قدرن تي مشتمل آهي ، هڪ وقت جي شروعات آهي ۽ ٻيو وقت ختم ڪرڻ وارو آهي. مسئلو بيان ڪرڻ لاءِ پڇندو آهي ته ڇا ڪو وقفو ڪنهن ٻئي جي مٿان چڙهندا آهن جيڪڏهن نق چڙهيل آهن ته پوءِ ڇا ، ڇا ، نه پر پرنٽ ڪريو.

مثال

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

وضاحت

ڇاڪاڻ ته ، وقت جو وقفو (2، 3) ۽ (1، 4) هڪ ٻئي تي چڙهندا آهن.

چڪاس ڪريو ته ڇا ٻه وقفي وقف ٿيل ڏنل وقف جي وچ ۾ اوورلوپ ٿي ويندا آهن

تصوير واضح طور تي ڏيکاري ٿي ته وقار (2,3،1,4) ۽ (XNUMX،XNUMX) اوورلوپ.

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

وضاحت

ڇاڪاڻ ته وقفن مان ڪو هڪٻئي کي مٿان چڙهائي نٿو سگهي.

الورورٿم

  1. ھڪڙي وقتي جي وڌ ۾ وڌ ختم ٿيڻ واري قيمت ڳوليو (وڌ ۾ وڌ عنصر).
  2. جيترو وڏو عنصر اسان کي مليو آهي اوت ئي ئي سائيز جي هڪ آرڊر ٺاهيو.
  3. ڏنل ان پٽ صف کي ترتيب ڏيو ، هر وقفي جي شروعاتي ۽ آخري قيمت حاصل ڪريو ،
  4. temp جي صف ۾ داخل ڪريو ۽ 1 وقت شروع ٿيندڙ قدر کي وڌايو ، ۽ 1 کي ختم ڪندي (ختم ٿيڻ واري وقت + 1) جي قدر.
  5. اسان وڌ کان وڌ عنصر کي لڪايو ، اسان لڌو
  6. پوئين قيمت ۽ موجوده قيمت کي ڳنيو ۽ ان کي ٽريم صف ۾ محفوظ ڪريو ، چڪاس ڪريو ته ڇا ڪا قيمت 1 کان وڌيڪ آهي ، پوءِ صحيح واپس اچو.
  7. غلط موٽڻ.

وضاحت

اسان جو مسئلو چيڪ ڪرڻ آهي ته ڇا ڪنهن ٻه وقفي مان هڪ وقف جي حد مقرر ڪئي ويندي آهي. تنهن ڪري ، اسان کي وقفو جو هڪ سيٽ ڏنو ويندو آهي ، هر وقفو ٻن قدرن تي مشتمل هوندو آهي ، هڪ ختم ٿيندڙ قيمت ۽ ٻيو هڪ وقتي قدر جي شروعاتي قيمت آهي. اسان کي اهو طئي ڪرڻو پوندو ته ڪي وقفي وڌيڪ چڙهيل آهن. جيڪڏهن ڪي وقتي اوورپلوپ ڪري رهيا آهن يا س interي وقفي کي coveringڪي رهيا آهن ، ته اسان کي ها پرنٽ ڪرڻ گهرجي ، ٻي صورت ۾ پرنٽ نه. ان لاءِ ، اسان وقت جي وقتي جا وڌ کان وڌ عنصر ڳولڻ وارا آهيون ، ڇاڪاڻ ته ختم ٿيڻ واري وقت هميشه وڌ کان وڌ هوندي آهي ، تنهن ڪري اسان ختم ٿيڻ واري وقت جي وڌ ۾ وڌ وڌ عنصر کي ڳوليندا رهياسين ، اسان هميشه اتي وڌ کان وڌ ويليو ڳوليندا آهيون.

ان کان پوءِ هڪ طبيب ٺاهيو صف ساڳئي سائيز جيتري قدر ڏنل آهي. وقتي طور تي شروعاتي ۽ ختم ٿيڻ واري وقت کي رکڻ لاءِ انهي صف کي استعمال ڪريو. پر ان کان اڳ ، اسان شروعات جي وقت ۽ وقفو جي وقتي وقت جي قدر حاصل ڪنداسين. وقتي وقت جي شروعات ۽ ختم ٿيڻ واري وقت کي ٽائم ۾ لڳايو ۽ شروعاتي وقت جو قدر 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

جاوا ڪوڊ interval overlapping کي چڪاس ڪرڻ جي لاءِ

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).

خلائي پيچيدگي

اي (وڌ کان وڌ انٽرنيشنل ٽائيم) ڇاڪاڻ ته اسان هڪ دريافت ڪرڻ لاءِ اسٽوري کي محفوظ ڪري رهيا آهيون ته ڪنهن خاص وقت تي ڪيترا وقفي ختم ٿي رهيا آهن.