Remove Interval

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
4 upvotes
Asked in company
Google inc

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.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
4
1 3
4 6
7 8
9 10
5 8
1
1 6
2 4

Sample Output 1 :

1 3
4 5
9 10
1 2
4 6

Explanation of Sample Input 1 :

Test case 1:
The given ranges are [ (1, 3), (4, 6), (7, 8), (9, 10)] and given ‘removeRange’ is (5, 8).
Below figure shows the remove operation on given ranges, ‘removeRange’ is shown in red color.

1

Test case 2:

1

Sample Input 2 :

1
2
5 10
10 12
1 15

Sample Output 2 :

-1

Explanation of Sample Input 2 :

The given ‘removeRange’ fully intersects with all ranges in the given list, thus we have to remove all ranges and return an empty list.
Hint

Check all points from minimum point to maximum point in the given range.

Approaches (2)
Brute Force 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.
Time Complexity

O(D * N ), where ‘D’ is the difference between the minimum and maximum points in the given list of ranges and ‘N’ is the total number of given ranges.

 

As we checking each point from minimum to maximum point in the given list of ranges, and a check operation takes O(N) times complexity in the worst case, hence the overall complexity will be O ( D* N ).

Space Complexity

O(N), where ‘N’ is the total number of given ranges.

 

In the worst case, the ‘answer’ array will store all the given ranges hence overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Remove Interval
Full screen
Console