Last Updated: 1 Apr, 2021

Remove Interval

Moderate

Asked in company

Solve now

Problem statement

You are given a sorted list of ‘N’ disjoint ranges of integers and a range ‘removeRange’. A range can be represented as [ ‘start’, ‘end’) where ‘end’ > ‘start’ and all the real numbers ‘x’ such that ( ‘start’ <= ‘x’ < ‘end’ ) belong to that range.

You need to remove all intersections between any range in the given list of ranges and range ‘removeRange’. Then return a resulting list of ranges in sorted order.

Note :

Here, Disjoint ranges mean that no two ranges from the given list intersect each other.

A list of ranges [ (X1, Y1), (X2, Y2), (X3, Y3) … (Xn, Yn) ] is sorted if and only if Xi > Xi-1  and as the given ranges are disjoint, so Xi > Yi-1 for each i [ 1 < i <= n].

Example :

Let ‘N’= 3, given list be [(1, 3), (4, 6), (8, 11) ], and ‘removeRange’ be (2, 8).

Then after removing all intersections between ranges in the list and ‘removeRange’.The list will look like [(1, 2), (8, 11) ].
As we have removed, 
Range (2,3) from the first range (1,3).
The whole second range (4, 6) as this is fully intersecting with the given ‘removeRange’
Nothing from the third range (8, 11) as no point is in this range is intersecting with the given ‘removeRange’ (2,8).

Note :

The resulting list after removing ranges can be empty also.

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases. The description of ‘T’ test cases follows

The first line of each test case contains an integer  ‘N’  representing the number of ranges in the given list.      
Next ‘N’ lines of the test case contain two space-separated integers, ‘start’ and ‘end’, denoting the starting and the ending point of the i-th range.

The last line of the test cases contains two space-separated integers, ‘start’ and ‘end’, denoting the starting and the ending point of the ‘removeRange’.

Output format :

For each test case, print ‘K’ lines containing two space-separated integers, ‘start’ and ‘end’, denoting the starting and the ending point of the ith range in the resulting list after removing ranges. Where ‘K’ is the size of the resulting list of ranges. If ‘K’ is 0 i.e. the resulting list does not contain any range then print ‘-1’

The output of each test case will be printed in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function. 

In the given function, you need to return a 2D array ‘arr[K][2]’, where ‘K’ is the number of ranges in the resulting list after removing ranges and ‘arr[i][0]’,  ‘arr[i][1]’ are the starting and ending points in the ‘i th’ range of resulting string.

Constraints :

1 <= T <= 5
1 <= N <= 3000
1 <= start <= end <= 10^9

Where ‘T’ is the total number of test cases, ‘N’ is the number of ranges, and ‘start’ and ‘end’ represent the first and the last integer of a range.

Time Limit : 1 sec

Solve now

Approaches

01 Approach

The idea here is to iterate over all points from minimum to maximum point in the given list of ranges and check if this point can be part of the range in the result list. The minimum point will be the ‘start’ point of the first range in the list and the maximum point will be the ‘end’ point of the last range in the given list because the given list is sorted. A point can only be included in the answer if and only if it lies in one of the given ranges and doesn’t lie on the given ‘removeRange’, else it cannot be included in the answer.

Algorithm:

Let the given list be ‘rangeList’ and range to remove be ‘removeRange’.
Declare a function say ‘check’ to check that if a point lies in any of the given range or not.
Declare two variables say ‘minPoint’, ‘maxPoint’ and ‘currPoint’
Set ‘minPoint’ to ‘rangeList [0][0]’ and ‘maxPoint’ to ‘rangeList [n-1] [1]’, where ‘n’ is the size of the list.
Set ‘currPoint’ to ‘minPoint’
Declare a list say ‘answer’ and a variable say ‘startPoint’ to keep track of the current range in the answer list and set ‘startPoint’ to -1
Run a loop until ‘currPoint’ is not greater than ‘maxPoint’
- If check( ‘currPoint’ ) is true and ‘currPoint’ doesn’t lie on ‘removeRange’
  - If ‘startPoint’ == -1, this means that the current point will be the start point for the range so, set ‘startPoint’ = ‘currpoint’
- Else
  - If ‘startPoint’ is not -1, this means that a range has already started and the current point will be the ‘endPoint’ for this range, so you can add [ ‘startPoint’, ‘currPoint’ ] to the ‘answer’ list and then set ‘startPoint’ to -1 again.
Return ‘answer’

Description of ‘check’ function

The function will take two parameters:

‘point’: an integer value.
‘List’: a 2D array of given ranges.

bool check ( ‘point’, ‘list’ ):

For each ‘range’ in the list:
- If ‘point’ >= ‘range [0]’ and ‘point’ < ‘range [1]’
  - Return True
Return False.

Solve now

02 Approach

For any range in the given list, there can be only one of the four below case

‘removeRange’ partially overlaps with the range.
‘removeRange’ does not overalls with the range.
Range completely lies under the ‘removeRange’
‘removeRange’ completely lies under the range.

All these cases can be handled easily as shown in the below figure. (red line denotes the given ‘removeRange’).

Algorithm:

Let the given list be ‘rangeList’ and range to remove be ‘removeRange’.
Declare a list say ‘answer’ to store the ranges of the resulting list.
Run a loop for each ‘currRange’ in given ‘rangeList’
- If ‘currRange’ partially overlaps with ‘removeRange’
  - If ‘currRange [0]’ < ‘removeRange [0]’, then add [‘currRange [0]’, ‘removeRange [0]’ ] in ‘answer’
  - Else, add [ ‘removeRange [1]’, ‘currRange [1]’ ] in ‘answer’.
- If ‘currRange [1]’ >= ‘removeRange [0]’ or ‘removeRange [1]’ > ‘currRange [0]’
  - This means no overlapping, so we add [ ‘currRange [0]’, ‘currRange [1]’ ] into ‘answer’.
- If ‘currRange [1]’ >= ‘removeRange [0]’ and ‘removeRange [1]’ <= ‘currRange [0]’
  - In this case, we need to add two ranges in the ‘answer’ by carefully handling some edge cases.
    - If ‘currRange [0]’ != ‘removeRange [0]’, then add [ ‘currRange [0]’, ‘removeRange [0]’ ].
    - If ‘currRange [1]’ != ‘removeRange [1]’, then add [ ‘removeRange [1]’, ‘currRange[1]’ ].
Return answer.

Solve now