Check if any two intervals overlap among a given set of intervals - GeeksQuiz

Check if any two intervals overlap among a given set of intervals - GeeksQuiz
An interval is represented as a combination of start time and end time. Given a set of intervals, check if any two intervals overlap.

// Compares two intervals according to their staring time.

// This is needed for sorting the intervals using library

// function std::sort(). See http:// goo.gl/iGspV

bool compareInterval(Interval i1, Interval i2)

{

    return (i1.start < i2.start) ? true : false;

}

  

// Function to check if any two intervals overlap

bool isOverlap(Interval arr[], int n)

{

    // Sort intervals in increasing order of start time

    sort(arr, arr + n - 1, compareInterval);

  

    // In the sorted array, if start time of an interval

    // is less than end of previous interval, then there

    // is an overlap

    for (int i = 1; i < n; i++)

        if (arr[i - 1].end > arr[i].start)

            return true;

  

    // If we reach here, then no overlap

    return false;

}

1. Find the overall maximum element. Let it be max_ele
2. Initialize an array of size max_ele with 0.
3. For every interval [start, end], increment the value at index start, i.e. arr[start]++ and decrement the value at index (end + 1), i.e. arr[end + 1]- -.
4. Compute the prefix sum of this array (arr[]).
5. Every index, i of this prefix sum array will tell how many times i has occurred in all the intervals taken together. If this value is greater than 1, then it occurs in 2 or more intervals.
6. So, simply initialize the result variable as false and while traversing the prefix sum array, change the result variable to true whenever the value at that index is greater than 1.

Time Complexity : O(max_ele + n)
Note: This method is more efficient than Method 1 if there are more number of intervals and at the same time maximum value among all intervals should be low, since time complexity is directly proportional to O(max_ele).

bool isOverlap(Interval arr[], int n)

{

  

    int max_ele = 0;

  

    // Find the overall maximum element

    for (int i = 0; i < n; i++) {

        if (max_ele < arr[i].end)

            max_ele = arr[i].end;

    }

  

    // Intialize an array of size max_ele

    int aux[max_ele + 1] = { 0 };

    for (int i = 0; i < n; i++) {

  

        // starting point of the interval

        int x = arr[i].start;

  

        // end point of the interval

        int y = arr[i].end;

        aux[x]++, aux[y + 1]--;

    }

    for (int i = 1; i <= max_ele; i++) {

        // Calculating the prefix Sum

        aux[i] += aux[i - 1];

  

        // Overlap

        if (aux[i] > 1)

            return true;

    }

  

    // If we reach here, then no Overlap

    return false;

}




Read full article from Check if any two intervals overlap among a given set of intervals - GeeksQuiz