ನಿರ್ದಿಷ್ಟ ಮಧ್ಯಂತರಗಳಲ್ಲಿ ಯಾವುದೇ ಎರಡು ಮಧ್ಯಂತರಗಳು ಅತಿಕ್ರಮಿಸುತ್ತವೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಆರ್ಸೆಸಿಯಮ್ ಸಿಸ್ಕೋ ಡೈರೆಕ್ಟಿ JP ಮೋರ್ಗಾನ್ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಕ್ವಾಲ್ಕಾಮ್ ಯಾಂಡೆಕ್ಸ್
ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ವಿಂಗಡಿಸಲಾಗುತ್ತಿದೆ

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

"ನಿರ್ದಿಷ್ಟ ಮಧ್ಯಂತರಗಳಲ್ಲಿ ಯಾವುದೇ ಎರಡು ಮಧ್ಯಂತರಗಳು ಅತಿಕ್ರಮಿಸುತ್ತವೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ" ಎಂಬ ಸಮಸ್ಯೆ ನಿಮಗೆ ಕೆಲವು ಮಧ್ಯಂತರಗಳನ್ನು ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಪ್ರತಿಯೊಂದು ಮಧ್ಯಂತರವು ಎರಡು ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಒಂದು ಪ್ರಾರಂಭದ ಸಮಯ ಮತ್ತು ಇನ್ನೊಂದು ಸಮಯ ಕೊನೆಗೊಳ್ಳುತ್ತದೆ. ಅತಿಕ್ರಮಿಸಿದರೆ ಯಾವುದೇ ಮಧ್ಯಂತರಗಳು ಒಂದರ ಮೇಲೊಂದರಂತೆ ಪರೀಕ್ಷಿಸಲು ಸಮಸ್ಯೆ ಹೇಳಿಕೆಯು ಕೇಳುತ್ತದೆ ಮತ್ತು ನಂತರ 'ಹೌದು' ಮುದ್ರಿಸಿ ಇಲ್ಲದಿದ್ದರೆ 'ಇಲ್ಲ' ಎಂದು ಮುದ್ರಿಸಿ.

ಉದಾಹರಣೆ

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 ಕ್ಕಿಂತ ಹೆಚ್ಚಿನ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿದೆಯೆ ಎಂದು ಪ್ರತಿ ಟ್ರಾವೆರ್ಸಲ್ ಪರಿಶೀಲನೆಗಾಗಿ, ಯಾವುದೇ ಅತಿಕ್ರಮಣಗಳು ಸಂಭವಿಸಿದೆಯೇ ಎಂದು ಇದು ಪರಿಶೀಲಿಸುತ್ತದೆ. ನಿಜ, ನಂತರ ನಿಜಕ್ಕೆ ಹಿಂತಿರುಗಿ. ಎಲ್ಲಾ ಅಡ್ಡಹಾಯುವಿಕೆಯನ್ನು ಮಾಡಿದ ನಂತರ, ಸುಳ್ಳನ್ನು ಹಿಂತಿರುಗಿ, ನಾವು ಈ ಸಾಲಿನಲ್ಲಿ ಇಲ್ಲಿಗೆ ಬಂದರೆ, ಯಾವುದೇ ಅತಿಕ್ರಮಣ ಸಂಭವಿಸುವುದಿಲ್ಲ. ಆದ್ದರಿಂದ ನಾವು ಸುಳ್ಳನ್ನು ಹಿಂತಿರುಗಿಸುತ್ತೇವೆ. ನೀವು ಒಮ್ಮೆ ನೋಡಲು ಬಯಸಿದರೆ, ಇದೇ ರೀತಿಯ ಸಮಸ್ಯೆ ಇದೆ, ಅದು ನಮ್ಮನ್ನು ಕೇಳುತ್ತದೆ ಅತಿಕ್ರಮಿಸುವ ಮಧ್ಯಂತರಗಳನ್ನು ವಿಲೀನಗೊಳಿಸಿ.

ಕೋಡ್

ಮಧ್ಯಂತರ ಅತಿಕ್ರಮಣವನ್ನು ಪರಿಶೀಲಿಸಲು ಸಿ ++ ಕೋಡ್

#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 (maxIntervalEndingTime) ಅಗತ್ಯವಿದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

O (maxIntervalEndingTime) ಏಕೆಂದರೆ ಒಂದು ನಿರ್ದಿಷ್ಟ ಸಮಯದಲ್ಲಿ ಎಷ್ಟು ಮಧ್ಯಂತರಗಳು ಅತಿಕ್ರಮಿಸುತ್ತಿವೆ ಎಂಬುದನ್ನು ಕಂಡುಹಿಡಿಯಲು ನಾವು ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಸಂಗ್ರಹಿಸುತ್ತಿದ್ದೇವೆ.