# Find if any two intervals overlap in given intervals

**Objective:** Interval is defined as [start, end]- the start of an interval to the end of the interval. Given a list of Intervals. Your task is to check if any two intervals overlap.

**Example:**

Given Interval: [[1,5], [6,10], [12,15], [3,7]] Two intervals are present which intersect Given Interval: [[1,5], [6,10], [12,15]] No intervals overlasx

**Approach: **

Naive solution: Compare each interval with all the other intervals and check if there is any overlap.

**Time complexity:** O(N^{2})

**Better Approach: Sorting**

Sort the given intervals as ascending order of their start time. Now Iterate through sorted intervals and check for any two adjacent intervals if the end of the first interval is greater than the start of the second interval (means before the first interval could end the second interval has started, so these two intervals overlap), if yes then we have found the overlap, break the loop.

**Time complexity: **O(nlogn)

**Complete Code:**

**Output:**

Given Interval: [[1,5], [6,10], [12,15]] No intervals overlap ------------------------------------------- Given Interval: [[1,5], [6,10], [12,15], [3,7]] Intervals are overlapping -------------------------------------------

**Best Approach: (If the last end time is not very high)**

- Find the max end time among all the intervals. Call it
.*last_end_time* - Create a
array of size =last_end_time+2*count[]* - Now iterate through all the intervals and for each interval put +1 at index
and put -1 at index count[end time + 1].*count[start time]* - Once the
array is filled, iterate through the count array and keep adding array values. If any time sum is greater than 1 means there is overlapping (Notice: If intervals are not overlapping then +1 for start of interval and -1 for end of the interval so sum becomes 0 if sum is greater than 1 means another interval started before existing interval ends.)*count[]*

**Time complexity:** O(N + last_end_time)

**Complete Code:**

**Output:**

Given Interval: [[1,5], [6,10], [12,15]] No intervals overlap ------------------------------------------- Given Interval: [[1,5], [6,10], [12,15], [3,7]] Intervals are overlapping