# Check if any two intervals intersects among a given set of intervals

• Difficulty Level : Easy
• Last Updated : 03 Jan, 2023

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 ` `#include ` `using` `namespace` `std;`   `// An interval has start time and end time` `struct` `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/iGspV` `bool` `compareInterval(Interval i1, Interval i2)` `{` `    ``return` `(i1.start < i2.start) ? ``true` `: ``false``;` `}`   `// Function to check if any two intervals overlap` `bool` `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 program` `int` `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 overlap` `import` `java.io.*;` `import` `java.lang.*;` `import` `java.util.*;`   `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)` `{`   `    ``// 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 code` `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 Kingash`

## Python3

 `# A Python program to check if any two intervals overlap`   `# An interval has start time and end time` `class` `Interval:` `    ``def` `__init__(``self``, start, end):` `        ``self``.start ``=` `start` `        ``self``.end ``=` `end`   `# Function to check if any two intervals overlap` `def` `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 code` `arr1 ``=` `[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

 ``

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 ` `#include ` `using` `namespace` `std;`   `// An interval has start time and end time` `struct` `Interval {` `    ``int` `start;` `    ``int` `end;` `};`   `// Function to check if any two intervals overlap` `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[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 program` `int` `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 time` `class` `Interval:` `    ``def` `__init__(``self``, start, end):` `        ``self``.start ``=` `start` `        ``self``.end ``=` `end`   `# Function to check if any two intervals overlap` `def` `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 program` `arr1 ``=` `[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 Code` `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))` `        ``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

 ``

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).
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}