Last Updated: 17 Jul, 2020
Overlapping Intervals
Easy
Asked in companies
You have been given the start and end times of 'N' intervals. Write a function to check if any two intervals overlap with each other.
Note :
If an interval ends at time T and another interval starts at the same time, they are not considered overlapping intervals.
Input format :
The first line contains an Integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first line of each test case or query contains an integer 'N' representing the total number of intervals.
The second line contains 'N' single space-separated integers representing the starting time of the intervals.
The third line contains 'N' single space-separated integers representing the end time of the intervals.
Output Format :
For each test case, return true if overlapping intervals are present. Otherwise, return false.
Output for every test case will be printed in a separate line.
Note :
You do not have to print anything. Just return the boolean value.
Constraints :
1 <= T <= 10^2
0 <= N <= 10^5
0 <= Start[i] <= 10^15
1 <= End[i] <= 10^15
Time Limit: 1 sec
Approaches
Iterate over the intervals one by one.
For every interval, check if there is an overlap with any of the remaining intervals then we stop execution
Sort the list of intervals first on the basis of their start time and then iterate through the array
If the start time of an interval is less than the end of the previous interval, then there is an overlap and we can return true.
If we iterate through the entire array without finding an overlap, we can return false
There is an alternative approach also possible in which we:
- Find the overall maximum endTime. Let it be maxElement
- Initialize an array (arr) of size (maxElement + 1) with 0.
- For every interval [startTime, endTime], increment the value at index startTime, i.e.
- arr[startTime]++ and decrement the value at index (endTime + 1), i.e. arr[endTime + 1]--.
- Compute the prefix sum of this array (arr).
- 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 more than 1 interval.
- 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.
This would work with a complexity of O(N + maxElement). But, this would not work for values greater than 10^8, hence this is not feasible here.