---
description: Merge Intervals
---

# Interval List Intersection

## Problem

Given two lists of intervals, find the **intersection of these two lists**. Each list consists of **disjoint intervals sorted on their start time**.

{% hint style="info" %}
For example:

```
Input: A = [[0,2],[5,10],[13,23],[24,25]], 
       B = [[1,5],[8,12],[15,24],[25,26]]
       
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
```
{% endhint %}

### Thought Process

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MNPhzQdDSv0oZZktWwL%2F-MNPuFyvc1mvNxGpMCQ-%2FIMG_1088151E0DF1-1.jpeg?alt=media\&token=14e97ad7-e8b1-4ef2-b2c2-773fc758ab69)

## Solution

```
class Solution:
    def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
        
        i, j = 0, 0
        res = []
        
        while i < len(A) and j < len(B):
            a_overlap = A[i][0] >= B[j][0] and A[i][0] <= B[j][1]
            b_overlap = B[j][0] >= A[i][0] and B[j][0] <= A[i][1]
            
            if(a_overlap or b_overlap):
                res.append([max(A[i][0], B[j][0]), min(A[i][1], B[j][1])])
            
            if A[i][1] < B[j][1]:
                i+=1
            else:
                j+=1
        return res
        
#We are comparing the intervals start times since we 
#don't know which interval start time is smaller 
between the two

#If two intervals intersect, we take the maximum start
#time and minimum end time


#Time: O(N+M)
#Space: O(1)
```

