An interval is represented as a combination of start time and end time. Given a set of intervals, check if any two intervals intersect.
Examples:
Input: arr[] = {{1, 3}, {5, 7}, {2, 4}, {6, 8}}
Output: true
The intervals {1, 3} and {2, 4} overlap
Input: arr[] = {{1, 3}, {7, 9}, {4, 6}, {10, 13}}
Output: false
No pair of intervals overlap.
Expected time complexity is O(nLogn) where n is number of intervals.
We strongly recommend to minimize your browser and try this yourself first.
A Simple Solution is to consider every pair of intervals and check if the pair intersects or not. The time complexity of this solution is O(n2)
Method 1
A better solution is to Use Sorting. Following is complete algorithm.
1) Sort all intervals in increasing order of start time. This step takes O(nLogn) time.
2) In the sorted array, if start time of an interval is less than end of previous interval, then there is an overlap. This step takes O(n) time.
So overall time complexity of the algorithm is O(nLogn) + O(n) which is O(nLogn).
Below is the implementation of above idea.
C++
// A C++ program to check if any two intervals overlap#include <algorithm>#include <iostream>using namespace std;// An interval has start time and end timestruct Interval { int start; int end;};// Compares two intervals according to their starting time.// This is needed for sorting the intervals using library// function std::sort(). See http:// goo.gl/iGspVbool compareInterval(Interval i1, Interval i2){ return (i1.start < i2.start) ? true : false;}// Function to check if any two intervals overlapbool isIntersect(Interval arr[], int n){ // Sort intervals in increasing order of start time sort(arr, arr + n , 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;}// Driver programint main(){ Interval arr1[] = { { 1, 3 }, { 7, 9 }, { 4, 6 }, { 10, 13 } }; int n1 = sizeof(arr1) / sizeof(arr1[0]); isIntersect(arr1, n1) ? cout << "Yes\n" : cout << "No\n"; Interval arr2[] = { { 6, 8 }, { 1, 3 }, { 2, 4 }, { 4, 7 } }; int n2 = sizeof(arr2) / sizeof(arr2[0]); isIntersect(arr2, n2) ? cout << "Yes\n" : cout << "No\n"; return 0;} |
Java
// A Java program to check if any two intervals overlapimport java.io.*;import java.lang.*;import java.util.*;class GFG{// An interval has start time and end timestatic class Interval{ int start; int end; public Interval(int start, int end) { super(); this.start = start; this.end = end; }};// Function to check if any two intervals overlapstatic boolean isIntersect(Interval arr[], int n){ // Sort intervals in increasing order of start time Arrays.sort(arr, (i1, i2) -> { return i1.start - i2.start; }); // 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;}// Driver codepublic static void main(String[] args){ Interval arr1[] = { new Interval(1, 3), new Interval(7, 9), new Interval(4, 6), new Interval(10, 13) }; int n1 = arr1.length; if (isIntersect(arr1, n1)) System.out.print("Yes\n"); else System.out.print("No\n"); Interval arr2[] = { new Interval(6, 8), new Interval(1, 3), new Interval(2, 4), new Interval(4, 7) }; int n2 = arr2.length; if (isIntersect(arr2, n2)) System.out.print("Yes\n"); else System.out.print("No\n");}}// This code is contributed by Kingash |
Python3
# A Python program to check if any two intervals overlap# An interval has start time and end timeclass Interval: def __init__(self, start, end): self.start = start self.end = end# Function to check if any two intervals overlapdef isIntersect(arr, n): # Sort intervals in increasing order of start time arr.sort(key=lambda x: x.start) # In the sorted array, if start time of an interval # is less than end of previous interval, then there # is an overlap for i in range(1, n): if (arr[i - 1].end > arr[i].start): return True # If we reach here, then no overlap return False# Driver codearr1 = [Interval(1, 3), Interval(7, 9), Interval(4, 6), Interval(10, 13)]n1 = len(arr1)if (isIntersect(arr1, n1)): print("Yes")else: print("No")arr2 = [Interval(6, 8), Interval(1, 3), Interval(2, 4), Interval(4, 7)]n2 = len(arr2)if (isIntersect(arr2, n2)): print("Yes")else: print("No")# This code is contributed by Saurabh Jaiswal |
C#
using System;using System.Linq;class GFG { // An interval has start time and end time class Interval { public int start; public int end; public Interval(int start, int end) { this.start = start; this.end = end; } } // Function to check if any two intervals overlap static bool IsIntersect(Interval[] arr, int n) { // Sort intervals in increasing order of start time Array.Sort(arr, (i1, i2) => i1.start.CompareTo(i2.start)); // 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; } // Driver Code static void Main(string[] args) { Interval[] arr1 = { new Interval(1, 3), new Interval(7, 9), new Interval(4, 6), new Interval(10, 13) }; int n1 = arr1.Length; if (IsIntersect(arr1, n1)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } Interval[] arr2 = { new Interval(6, 8), new Interval(1, 3), new Interval(2, 4), new Interval(4, 7) }; int n2 = arr2.Length; if (IsIntersect(arr2, n2)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } }}// This code is contributed by phasing17 |
Javascript
<script>// A Javascript program to check if any two intervals overlap// An interval has start time and end timeclass Interval{ constructor(start,end) { this.start = start; this.end = end; }}// Function to check if any two intervals overlapfunction isIntersect(arr,n){ // Sort intervals in increasing order of start time arr.sort(function(i1, i2){ return i1.start - i2.start; }); // In the sorted array, if start time of an interval // is less than end of previous interval, then there // is an overlap for(let i = 1; i < n; i++) if (arr[i - 1].end > arr[i].start) return true; // If we reach here, then no overlap return false;}// Driver codelet arr1=[new Interval(1, 3), new Interval(7, 9), new Interval(4, 6), new Interval(10, 13) ];let n1 = arr1.length;if (isIntersect(arr1, n1)) document.write("Yes<br>");else document.write("No<br>");let arr2 = [ new Interval(6, 8),new Interval(1, 3),new Interval(2, 4),new Interval(4, 7) ];let n2 = arr2.length;if (isIntersect(arr2, n2)) document.write("Yes<br>");else document.write("No<br>");// This code is contributed by rag2127</script> |
Output:
No Yes
Time Complexity: O(nlogn)
Auxiliary Space: O(1)
Method 2: This approach is suggested by Anjali Agarwal. Following are the steps:
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.
Below is the implementation of this (Method 2) approach.
C++
// A C++ program to check if any two intervals overlap#include <algorithm>#include <iostream>using namespace std;// An interval has start time and end timestruct Interval { int start; int end;};// Function to check if any two intervals overlapbool isIntersect(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; } // Initialize 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;}// Driver programint main(){ Interval arr1[] = { { 1, 3 }, { 7, 9 }, { 4, 6 }, { 10, 13 } }; int n1 = sizeof(arr1) / sizeof(arr1[0]); isIntersect(arr1, n1) ? cout << "Yes\n" : cout << "No\n"; Interval arr2[] = { { 6, 8 }, { 1, 3 }, { 2, 4 }, { 4, 7 } }; int n2 = sizeof(arr2) / sizeof(arr2[0]); isIntersect(arr2, n2) ? cout << "Yes\n" : cout << "No\n"; return 0;}// This Code is written by Anjali Agarwal |
Java
// A Java program to check if any two intervals overlap class GFG{ // An interval has start time and end time static class Interval { int start; int end; public Interval(int start, int end) { super(); this.start = start; this.end = end; } }; // Function to check if any two intervals overlap static boolean isIntersect(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; } // Initialize an array of size max_ele int []aux = new int[max_ele + 1]; 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 ]--; } 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; } // Driver program public static void main(String[] args) { Interval arr1[] = { new Interval(1, 3), new Interval(7, 9), new Interval(4, 6), new Interval(10, 13) }; int n1 = arr1.length; if(isIntersect(arr1, n1)) System.out.print("Yes\n"); else System.out.print("No\n"); Interval arr2[] = { new Interval(6, 8), new Interval(1, 3), new Interval(2, 4), new Interval(4, 7) }; int n2 = arr2.length; if(isIntersect(arr2, n2)) System.out.print("Yes\n"); else System.out.print("No\n");}} // This code is contributed by 29AjayKumar |
Python3
# A Python program to check if any two intervals overlap# An interval has start time and end timeclass Interval: def __init__(self, start, end): self.start = start self.end = end# Function to check if any two intervals overlapdef is_intersect(arr, n): max_ele = 0 # Find the overall maximum element for i in range(n): if max_ele < arr[i].end: max_ele = arr[i].end # Initialize an array of size max_ele aux = [0] * (max_ele + 1) for i in range(max_ele + 1): aux[i] = 0 for i in range(n): # starting point of the interval x = arr[i].start # end point of the interval y = arr[i].end aux[x] += 1 aux[y] -= 1 for i in range(1, max_ele + 1): # 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# Driver programarr1 = [Interval(1, 3), Interval(7, 9), Interval(4, 6), Interval(10, 13)]n1 = len(arr1)if is_intersect(arr1, n1): print("Yes")else: print("No")arr2 = [Interval(6, 8), Interval(1, 3), Interval(2, 4), Interval(4, 7)]n2 = len(arr2)if is_intersect(arr2, n2): print("Yes")else: print("No") # this code is contributed by phasing17 |
C#
// C# program to check if// any two intervals overlap using System;class GFG{ // An interval has start time and end time class Interval { public int start; public int end; public Interval(int start, int end) { this.start = start; this.end = end; } }; // Function to check if// any two intervals overlap static bool isIntersect(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; } // Initialize an array of size max_ele int []aux = new int[max_ele + 1]; 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 ]--; } 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; } // Driver Codepublic static void Main(String[] args) { Interval []arr1 = { new Interval(1, 3), new Interval(7, 9), new Interval(4, 6), new Interval(10, 13) }; int n1 = arr1.Length; if(isIntersect(arr1, n1)) Console.Write("Yes\n"); else Console.Write("No\n"); Interval []arr2 = { new Interval(6, 8), new Interval(1, 3), new Interval(2, 4), new Interval(4, 7) }; int n2 = arr2.Length; if(isIntersect(arr2, n2)) Console.Write("Yes\n"); else Console.Write("No\n");}}// This code is contributed by Rajput-Ji |
Javascript
<script>// A Javascript program to check if any two intervals overlap// An interval has start time and end timeclass Interval{ constructor(start, end) { this.start = start; this.end = end; }}// Function to check if any two intervals overlapfunction isIntersect(arr, n){ let max_ele = 0; // Find the overall maximum element for (let i = 0; i < n; i++) { if (max_ele < arr[i].end) max_ele = arr[i].end; } // Initialize an array of size max_ele let aux = new Array(max_ele + 1); for(let i=0;i<(max_ele + 1);i++) { aux[i]=0; } for (let i = 0; i < n; i++) { // starting point of the interval let x = arr[i].start; // end point of the interval let y = arr[i].end; aux[x]++; aux[y ]--; } for (let 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;}// Driver programlet arr1 = [new Interval(1, 3), new Interval(7, 9), new Interval(4, 6), new Interval(10, 13)];let n1 = arr1.length;if(isIntersect(arr1, n1)) document.write("Yes<br>"); else document.write("No<br>"); let arr2 = [ new Interval(6, 8), new Interval(1, 3), new Interval(2, 4), new Interval(4, 7) ]; let n2 = arr2.length; if(isIntersect(arr2, n2)) document.write("Yes<br>"); else document.write("No<br>");// This code is contributed by avanitrachhadiya2155</script> |
Output:
No Yes
Time Complexity : O(max_ele + n)
Auxiliary Space: O(max_ele)
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).
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
