# Interval List Intersection

Posted: 25 Jan, 2021

Difficulty: Easy

#### 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].

#### 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]].

##### 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
```

SIMILAR PROBLEMS

Iruka And Marks

Posted: 5 Jul, 2022

Difficulty: Easy

Best time to buy and sell stock

Posted: 2 Sep, 2022

Difficulty: Moderate

Best time to buy and sell stock II

Posted: 5 Sep, 2022

Difficulty: Moderate

Array Rotation

Posted: 21 Oct, 2022

Difficulty: Easy

Find The Single Element

Posted: 30 Oct, 2022

Difficulty: Easy