Interval List Intersection

Easy
0/40
Average time to solve is 15m
6 upvotes
Asked in companies
FacebookIntuitAmerican Express

Problem statement

You have been given two sorted arrays/lists of closed intervals ‘INTERVAL1’ and ‘INTERVAL2’. A closed interval [x, y] with x < y denotes the set of real numbers ‘z’ with x <= z <= y.

Now, your task is to find the intersection of these two interval lists.

The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [0, 2] and [1, 3] is [1, 2].

Input

Note :

1. Each list of intervals is pairwise disjoint.
2. 'INTERVAL1' and 'INTERVAL2' don't contain duplicate intervals.
3. If there is no intersection present in 'INTERVAL1' and 'INTERVAL2' return an empty array/list.

For example, if INTERVAL1 = [[0, 5], [7, 9], [10, 11]] and INTERVAL2 = [[0, 2], [3, 7], [12, 15]], then the intersection array/list will be [[0, 2], [3, 5], [7, 7]].

Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input 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 contains two single-space separated integers ‘N1’ and ‘N2’, representing the length of ‘INTERVAL1 ’ and ‘INTERVAL2’ respectively.

The second line of each test case contains ‘2 * N1’ single space-separated integers denoting the intervals of the array/list INTERVAL1.

The third line of each test case contains ‘2 * N2’ single space-separated integers denoting the intervals of the array/list INTERVAL2.
Output Format : 
Print the list/array of intervals of the intersection of ‘INTERVAL1’ and ‘INTERVAL1’.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
0 <= N1 <= 5000
0 <= N2 <= 5000 
0 <= INTERVAL1[i][0] <=10^5
INTERVAL1[i][0] < INTERVAL1[i][1] <= 10^5
0 <= INTERVAL2[i][0] <=10^5
INTERVAL2[i][0] < INTERVAL2[i][1] <= 10^5

where 'T' denotes the number of test cases to be run, 'N1' and 'N2' denote the sizes of 'INTERVAL1' and 'INTERVAL2' respectively.

Time Limit: 1 second
Sample Input 1:
2
2 3
2 8 12 16
5 9 10 12 14 15
3 0
1 2 4 6 8 12
Sample output 1:
5 8 12 12 14 15
Explanation of Sample output 1:
For the first test case, INTERVAL1 is [[2, 8], [12, 16]] and INTERVAL2 is [[5, 9], [10, 12], [14, 15]] the intersections between INTERVAL1 and INTERVAL2 are [5 , 8], [12, 12] and [14, 15].
For the second test case, since there is no interval present in INTERVAL2 hence there is no intersection.
Sample Input 2:
2
2 2
2 4 8 10
5 7 11 14
1 1
2 4
2 4
Sample output 2:
2 4
Hint

Try to use a two-pointer technique.

Approaches (1)
Two-Pointer Approach

The main intuition behind this approach is that ‘INTERVAL1’ and ‘INTERVAL2’ are already sorted. So two cases arise:

 

  1. If INTERVAL1[0] has the smallest endpoint, it can only intersect INTERVAL2[0]. After that, we can discard INTERVAL1[0] since it cannot intersect with anything else.
  2. If INTERVAL2[0] has the smallest endpoint, it can only intersect INTERVAL1[0]. After that can discard INTERVAL2[0] since it cannot intersect with anything else.

 

Hence we can use a two-pointer algorithm.

Here is the algorithm:

 

  1. Initialise two integer variables ‘i’ and ‘j’ that iterate over ‘INTERVAL1’ and ‘INTERVAL2’ respectively. Also initialise vector ‘intersection’ that stores the result.
    1. Find the maximum of INTERVAL1[i][0] and INTERVAL2[j][0] i.e. ‘startInterval’ and minimum ofINTERVAL1[i][1] andINTERVAL2[j][1] i.e. ‘endInterval’.
    2. If startInterval <= endInterval
      1. Push vector {startInterval, endInterval} in ‘intersection’.
    3. If INTERVAL1[i][1] < INTERVAL2[j][1]
      1. i++
    4. Else
      1. j++
  2. Finally, we return intersection.
Time Complexity

O(N1 + N2), where ‘N1’ and ‘N2’ is the length of ‘INTERVAL1’ and ‘INTERVAL2’ respectively. 

 

We are iterating over ‘INTERVAL1’ and ‘INTERVAL2’. Hence, the time complexity is O(N1 + N2).

Space Complexity

O(1), i.e. constant space complexity. 

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