Isolated Intervals Finder

Easy

0/40

0 upvote

Problem statement

You are given a 2D array arr representing a collection of N intervals, where each interval is of the form [start, end].

Your task is to identify and return all the "isolated" intervals. An interval is considered isolated if it does not overlap with any other interval in the given set.

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

Input Format:

The first line of input contains an integer 'N', the number of intervals.

The next 'N' lines each contain two space-separated integers, start and end, representing an interval.

Output Format:

Print the isolated intervals, one per line, with the start and end values separated by a space.

The output intervals must be sorted in ascending order based on their start times.

If no isolated intervals exist, print a single line with the value -1.

Note:

Two intervals [s1, e1] and [s2, e2] are considered to overlap if s1 <= e2 and s2 <= e1. This means they also overlap if they just "touch" at an endpoint (e.g., [1, 5] and [5, 10]).

The most efficient way to solve this is to first sort all intervals by their start times. Then, for each interval, you only need to check for overlaps with its immediate neighbors in the sorted list.

Sample Input 1:

Sample Output 1:

1 2
3 4
5 6

Explanation for Sample 1:

The intervals are `[1,2]`, `[3,4]`, and `[5,6]`. None of these intervals overlap with any other, so all three are considered isolated. They are printed in sorted order.

Sample Input 2:

Sample Output 2:

8 10

Explanation for Sample 2:

- The interval `[1, 5]` overlaps with `[2, 6]`.
- The interval `[2, 6]` overlaps with `[1, 5]`.
- The interval `[8, 10]` does not overlap with `[1, 5]` or `[2, 6]`.
Therefore, only `[8, 10]` is an isolated interval.

Expected Time Complexity:

The expected time complexity is O(N log N).

Constraints:

1 <= N <= 10^5
-10^9 <= start <= end <= 10^9

Time limit: 1 sec

Approaches (1)

Approach 1

Isolated Intervals Finder

Time Complexity

Space Complexity

(100% EXP penalty)

Isolated Intervals Finder

Console