Overlapping Intervals

Easy

0/40

Average time to solve is 24m

Contributed by

58 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

Sample Output 1 :

false

Explanation For Sample Input 1:

Here, in given intervals [1, 2], [2, 3], [3, 4], there are no overlapping intervals present.

Sample Input 2 :

Sample Output 2 :

false
true

Hint 1

Hint 2

A very naive way to look at this would be to pick an interval and check it with every other interval for overlap.

Approaches (2)

Approach 1

Approach 2

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

Time Complexity

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.

Space Complexity

O(1)

Since we don't use any extra space.

(100% EXP penalty)

Overlapping Intervals

Console