Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Insert Interval

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
13 upvotes
Asked in companies
FacebookSamsungAdPushup

Problem statement

You are given a 2-dimensional array ‘Intervals’ containing a list of non-overlapping intervals sorted by their start time. You are given an interval ‘newInterval’. Your task is to insert the given interval at the correct position and merge all necessary intervals to produce a list with only mutually exclusive intervals.

For Example:
Consider 'Intervals' = [[1, 3], [5, 7], [8, 12]], and 'newInterval' = [4, 6] 
The interval [4, 6] overlaps with [5, 7]. Therefore we can merge the intervals and produce an interval [4, 7]. Hence the answer [[1,3], [4,7], [8,12]]
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
1 <= T <= 5
0 <= N <= 10^5
0 <= Intervals[i][0], Intervals[i][1] <= 10^10
0 <= newInterval[0], newInterval[1] <= 10^10

Time Limit: 1 sec
Sample Input 1:
2
3
1 3
5 7
8 12
4 6
3
1 3
5 7
8 12
4 10
Sample Output 1:
1 3
4 7
8 12
1 3
4 12
Explanation:
For the first test case,
The interval [4, 6] overlaps with [5, 7]. Therefore we can merge the intervals and produce an interval [4, 7]. Hence the answer [[1,3], [4,7], [8,12]].

For the second test case, 
The interval [4, 10] overlaps with [5, 7] and [8, 12]. Therefore we can merge the intervals and produce an interval [4, 12]. Hence the answer is [[1, 3], [4, 12]].
Sample Input 2:
2
2
2 3
5 7
1 4
2
1 2
6 9
3 5
Sample Output 2:
1 4
5 7
1 2
3 5
6 9
Full screen
Console