New update is available. Click here to update.

Last Updated: 25 Jan, 2021

Difficulty: Easy

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

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

```
Print the list/array of intervals of the intersection of ‘INTERVAL1’ and ‘INTERVAL1’.
Print the output of each test case in a separate line.
```

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

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

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

- 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.
- 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:

- Initialise two integer variables
*‘i’*and*‘j’*that iterate over*‘INTERVAL1’*and*‘INTERVAL2’*respectively. Also initialise vector*‘intersection’*that stores the result.- 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’*. - If
*startInterval*<=*endInterval*- Push vector {
*startInterval*,*endInterval*} in*‘intersection’*.

- Push vector {
- If
*INTERVAL1[i][1]*<*INTERVAL2[j][1]**i++*

- Else
*j++*

- Find the maximum of
- Finally, we return
*intersection*.

SIMILAR PROBLEMS

Missing Number

Posted: 30 Oct, 2022

Difficulty: Easy

Longest Subarray With Zero Sum

Posted: 3 Nov, 2022

Difficulty: Moderate

Merge Two Sorted Arrays Without Extra Space

Posted: 19 Nov, 2022

Difficulty: Moderate

Ninja And The Strictly Increasing Array

Posted: 27 Nov, 2022

Difficulty: Moderate

Negative To The End

Posted: 16 Dec, 2022

Difficulty: Easy

Popular Interview Problems: