بررسی کنید که آیا هر دو فواصل در یک مجموعه فواصل مشخص همپوشانی دارند


سطح دشواری متوسط
اغلب در آمازون ارسیسیوم سیسکو دیرتی JP مورگان مایکروسافت سامسونگ Yandex
برنامه نویسی پویا مرتب سازی

بیان مسأله

مسئله "بررسی کنید که آیا هر دو فواصل در یک مجموعه مشخص از فواصل با هم تداخل دارند" بیان می کند که یک سری فواصل به شما داده شده است. هر بازه از دو مقدار تشکیل شده است ، یکی زمان شروع و دیگری زمان پایان. بیانیه مسئله می خواهد بررسی کند که آیا هر یک از فواصل با هم تداخل دارند در صورت همپوشانی ، سپس "YES" را چاپ کنید در غیر این صورت "NO" را چاپ کنید

مثال

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. مقدار قبلی و مقدار فعلی را جمع کنید و آن را در آرایه temp ذخیره کنید ، بررسی کنید که آیا مقداری از 1 بیشتر است یا خیر ، درست را برگردانید.
  7. برگشت نادرست.

توضیح

مشکل ما این است که بررسی کنیم آیا هر دو فاصله در یک مجموعه مشخص از بازه ها همپوشانی دارند یا خیر. بنابراین ، مجموعه ای از بازه ها به ما داده می شود ، هر بازه از دو مقدار تشکیل شده است ، یکی مقدار انتهایی و دیگری مقدار شروع یک بازه زمانی. ما باید تعیین کنیم که آیا هر یک از فواصل با هم تداخل دارند. اگر هر یک از فواصل با هم تداخل دارند یا کل بازه را پوشش می دهند ، پس ما باید بله چاپ کنیم ، در غیر این صورت چاپ خیر. برای این ، ما می خواهیم بیشترین عنصر فاصله زمانی را پیدا کنیم ، زیرا زمان پایان همیشه بیشترین است ، بنابراین ما در جستجوی بیشترین عنصر در فاصله زمانی پایان خواهیم بود ، ما همیشه حداکثر مقدار را در آنجا پیدا می کنیم.

بعد از این یک دما ایجاد کنید صف دارای همان اندازه مقدار آرایه داده شده. از این آرایه برای قرار دادن زمان شروع و پایان فاصله استفاده کنید. اما قبل از آن ، مقادیر زمان شروع و زمان پایان فاصله را بدست خواهیم آورد. زمان شروع و زمان پایان این فاصله را در temp قرار دهید و مقدار زمان شروع را 1 افزایش دهید و مقدار (زمان پایان + 1) را 1 کاهش دهید و آرایه temp را به روز کنید.

ما می خواهیم آرایه temp ایجاد شده را رد کرده و حداکثر عنصری را که در ابتدای کد پیدا کردیم به روز کنیم. سپس بعد از اضافه کردن مقدار فعلی و مقدار قبلی آرایه temp ، برای هر پیمایش بررسی کنید که آیا هر یک از مقدار به روز شده دارای مقدار بزرگتر از 1 است ، این بررسی می کند که آیا هر یک از همپوشانی ها وجود دارد ، درست است ، سپس درست برگردید. بعد از اینکه همه تراورس انجام شد ، اگر در این خط به اینجا بیاییم ، false برگردید ، یعنی هیچ تداخلی رخ نمی دهد. بنابراین ما نادرست باز خواهیم گشت. اگر می خواهید نگاهی بیندازید ، مشکلی مشابه وجود دارد که از ما می خواهد فواصل همپوشانی را ادغام کنید.

رمز

کد ++ 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 (N) هزینه دارد. و سپس ایجاد آرایه پیشوند به O (maxIntervalEndingTime) نیاز دارد.

پیچیدگی فضا

O (maxIntervalEndingTime) زیرا ما آرایه ای را برای یافتن این که چند بازه در یک زمان خاص با هم تداخل دارند ذخیره کرده ایم.