تحقق مما إذا كان هناك أي فترتين متداخلتين بين مجموعة معينة من الفواصل الزمنية


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون Arcesium سيسكو Directi JP مورغان Microsoft كوالكوم ياندكس
البرمجة الديناميكية فرز

المشكلة بيان

توضح مشكلة "التحقق مما إذا كان هناك أي فواصل زمنية متداخلة بين مجموعة معينة من الفواصل الزمنية" أنك تحصل على مجموعة من الفواصل الزمنية. يتكون كل فاصل زمني من قيمتين ، إحداهما هي وقت البدء والأخرى تنتهي بالوقت. تطلب عبارة المشكلة التحقق مما إذا كان أي من الفواصل الزمنية يتداخل مع بعضها البعض إذا تداخلت ، ثم اطبع "نعم" وإلا اطبع "لا".

مثال

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. أدخل في المصفوفة المؤقتة وقم بزيادة قيمة وقت البدء بمقدار 1 ، وقم بتقليل قيمة (وقت الانتهاء + 1) بمقدار 1.
  5. اجتياز المصفوفة إلى أقصى عنصر وجدنا ،
  6. قم بتلخيص القيمة السابقة والقيمة الحالية وتخزينها في المصفوفة المؤقتة ، وتحقق مما إذا كانت أي قيمة أكبر من 1 ، ثم أعد القيمة true.
  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

تحليل التعقيد

تعقيد الوقت

O (maxIntervalEndingTime + n) أين "ن" هو عدد العناصر في المصفوفة. أولاً ، نجد الحد الأقصى للفاصل الزمني الذي كلفنا هذا الوقت O (N). ثم يتطلب إنشاء مجموعة البادئة O (maxIntervalEndingTime).

تعقيد الفضاء

O (maxIntervalEndingTime) لأننا قمنا بتخزين مصفوفة لمعرفة عدد الفواصل الزمنية المتداخلة في وقت معين.