This post is completed by 4 users

  • 0
 Add to List
Medium

470. 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(N2)

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)

 

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)

  1. Find the max end time among all the intervals. Call it last_end_time.
  2. Create a count[] array of size =last_end_time+1
  3. Now iterate through all the intervals and for each interval put +1 at index count[start time] and put -1 at index count[end time].
  4. Once the count[] 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.)

Time complexity: O(N + last_end_time)

 

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

Related Problems: