Overlapping Intervals
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

Question

Overlapping Intervals

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

Accepted Answer

It's the standard interval scheduling problem.

Accepted Answer

Brute Force

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

Space Complexity: O(1)Explanation:

O(1)

Since we don't use any extra space.

Time Complexity: O(n^2)Explanation:

O(N ^ 2) Where N is the total number of intervals.

For every interval, we check the remaining (N - i - 1) intervals where i is the current interval we are looking at. This would lead to polynomial time.

Accepted Answer

Sorting Approach

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.

Space Complexity: O(n)Explanation:

O(N), where N is the total number of intervals.

Sorting takes O(N) extra space.

Time Complexity: O(nlogn)Explanation:

O(N * logN), where N is the total number of intervals.

Sorting the list would take O(N * logN) operations

Later, iterating over the list again to find the overlap would take n operation hence the overall time complexity boils down to O(N * logN)

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 :

Input format :

Output Format :

Note :

Constraints :

Top SAP Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in SAP Software Developer