# Interval List Intersections
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/interval-list-intersections)
Canonical: https://scaleengineer.com/dsa/problems/interval-list-intersections
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Line Sweep](https://scaleengineer.com/dsa/patterns/line-sweep)
**Data structures:** Array
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [Yandex](https://scaleengineer.com/companies/yandex), [Verkada](https://scaleengineer.com/companies/verkada), [Nuro](https://scaleengineer.com/companies/nuro), [Mixpanel](https://scaleengineer.com/companies/mixpanel)
---
## Problem
You are given two lists of closed intervals, `firstList` and `secondList`, where `firstList[i] = [starti, endi]` and `secondList[j] = [startj, endj]`. Each list of intervals is pairwise **disjoint** and in **sorted order**.

Return _the intersection of these two interval lists_.

A **closed interval** `[a, b]` (with `a <= b`) denotes the set of real numbers `x` with `a <= x <= b`.

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 `[1, 3]` and `[2, 4]` is `[2, 3]`.

**Example 1:**

![](https://assets.glich.co/dsa/interval-list-intersections/image0.png) 

**Input:** firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
**Output:** [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

**Example 2:**

**Input:** firstList = [[1,3],[5,9]], secondList = []
**Output:** []

**Constraints:**

* `0 <= firstList.length, secondList.length <= 1000`
* `firstList.length + secondList.length >= 1`
* `0 <= starti < endi <= 109`
* `endi < starti+1`
* `0 <= startj < endj <= 109 `
* `endj < startj+1`

# Approaches
## Brute Force (Nested Loops)
This approach involves iterating through every interval in the first list and comparing it with every interval in the second list to find all possible intersections. It's straightforward but inefficient as it doesn't leverage the sorted nature of the input lists.
**Time:** O(N * M), where N is the length of `firstList` and M is the length of `secondList`. This is because for each of the N intervals in the first list, we iterate through all M intervals in the second list. · **Space:** O(K), where K is the number of intersections found. This space is used to store the resulting list of intervals. In the worst case, K can be up to N + M. If the output array is not considered, the space complexity is O(1).
**Pros:** Simple to conceptualize and implement.; Correctly finds all intersections regardless of input order (though the problem specifies sorted input).
**Cons:** Highly inefficient, especially for large lists, with a quadratic time complexity.; Ignores the crucial information that the input lists are sorted and disjoint, leading to many redundant comparisons.
### Explanation
The core idea of the brute-force approach is to check every possible pair of intervals, one from each list. We use nested loops to achieve this. The outer loop iterates through `firstList`, and the inner loop iterates through `secondList`. For each pair of intervals, we calculate their potential intersection.

An intersection between two intervals `[a, b]` and `[c, d]` exists if they overlap. The resulting intersection interval would be `[max(a, c), min(b, d)]`. A valid intersection exists only if the start of this new interval is less than or equal to its end. If it is, we add this intersection interval to our result list.

This method is exhaustive and guarantees finding all intersections, but it performs many unnecessary comparisons. For example, if `firstList[i]` ends before `secondList[j]` starts, this approach will still check `firstList[i]` against all subsequent intervals in `secondList` unnecessarily.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> intersections = new ArrayList<>();
        if (firstList == null || firstList.length == 0 || secondList == null || secondList.length == 0) {
            return new int[0][];
        }

        for (int[] interval1 : firstList) {
            for (int[] interval2 : secondList) {
                // Calculate the intersection
                int start = Math.max(interval1[0], interval2[0]);
                int end = Math.min(interval1[1], interval2[1]);

                // Check if there is a valid overlap
                if (start <= end) {
                    intersections.add(new int[]{start, end});
                }
            }
        }

        return intersections.toArray(new int[intersections.size()][]);
    }
}
```
### Algorithm
- Initialize an empty list, `result`, to store the intersection intervals.
- Use a nested loop. The outer loop iterates through each interval `A` from `firstList`.
- The inner loop iterates through each interval `B` from `secondList`.
- For each pair `(A, B)`, calculate the potential intersection. The start of the intersection is the maximum of the start points of `A` and `B`. The end of the intersection is the minimum of the end points of `A` and `B`.
- Let `A = [startA, endA]` and `B = [startB, endB]`. The intersection is `[max(startA, startB), min(endA, endB)]`.
- If the calculated start is less than or equal to the calculated end, it's a valid, non-empty intersection. Add this new interval to the `result` list.
- After both loops complete, return the `result` list.

## Two Pointers (Merge-like Approach)
A much more efficient approach that leverages the fact that both interval lists are sorted. It uses two pointers, one for each list, and iterates through them simultaneously, similar to the merge step of a merge sort algorithm. This avoids redundant comparisons and achieves linear time complexity.
**Time:** O(N + M), where N is the length of `firstList` and M is the length of `secondList`. Each pointer traverses its respective list only once, making the approach linear in the total number of intervals. · **Space:** O(K), where K is the number of intersections found. This space is required for the output list. Excluding the result, the space complexity is O(1).
**Pros:** Optimal time complexity.; Efficiently utilizes the sorted property of the input lists.; Simple to implement once the logic is understood.
**Cons:** Relies on the input lists being sorted. If they were not, they would need to be sorted first, adding an O(N log N + M log M) preprocessing step.
### Explanation
This optimal approach takes advantage of the sorted nature of the input lists. We can think of this as merging two sorted lists. We use two pointers, `i` and `j`, to iterate through `firstList` and `secondList` respectively.

At each step, we compare the intervals `firstList[i]` and `secondList[j]`.
1.  We find the overlap between these two intervals. The start of the overlap is the maximum of their start times, and the end is the minimum of their end times.
2.  If the start of the overlap is less than or equal to its end, we have found a valid intersection, and we add it to our result list.
3.  After checking for an intersection, we need to decide which pointer to advance. The key insight is to discard the interval that finishes earlier. If `firstList[i]` ends before `secondList[j]`, then `firstList[i]` cannot possibly overlap with any subsequent intervals in `secondList` (since `secondList` is sorted). Thus, we can safely move on from `firstList[i]` by incrementing `i`. Similarly, if `secondList[j]` ends earlier or at the same time, we increment `j`.

We repeat this process until one of the pointers goes past the end of its list. This ensures that each interval is processed only once, leading to a linear time complexity.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> intersections = new ArrayList<>();
        if (firstList == null || firstList.length == 0 || secondList == null || secondList.length == 0) {
            return new int[0][];
        }

        int i = 0; // pointer for firstList
        int j = 0; // pointer for secondList

        while (i < firstList.length && j < secondList.length) {
            int[] interval1 = firstList[i];
            int[] interval2 = secondList[j];

            // Find the intersection
            // lo is the maximum of the start points
            int lo = Math.max(interval1[0], interval2[0]);
            // hi is the minimum of the end points
            int hi = Math.min(interval1[1], interval2[1]);

            if (lo <= hi) {
                intersections.add(new int[]{lo, hi});
            }

            // Move the pointer that points to the interval that ends first
            if (interval1[1] < interval2[1]) {
                i++;
            } else {
                j++;
            }
        }

        return intersections.toArray(new int[intersections.size()][]);
    }
}
```
### Algorithm
- Initialize two pointers, `i = 0` for `firstList` and `j = 0` for `secondList`.
- Initialize an empty list, `result`, to store the intersection intervals.
- Loop as long as both pointers `i` and `j` are within the bounds of their respective lists (`i < firstList.length` and `j < secondList.length`).
- In each iteration, get the current intervals: `intervalA = firstList[i]` and `intervalB = secondList[j]`.
- Calculate the potential intersection: `start = max(intervalA[0], intervalB[0])` and `end = min(intervalA[1], intervalB[1])`.
- If `start <= end`, a valid intersection exists. Add the interval `[start, end]` to the `result` list.
- To decide which pointer to advance, compare the end points of the current intervals. If `intervalA` ends before `intervalB` (`intervalA[1] < intervalB[1]`), increment `i`. Otherwise, increment `j`.
- Once the loop finishes, return the `result` list.

# Solutions
### Java

```java
class Solution {
public
  int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
    List<int[]> ans = new ArrayList<>();
    int m = firstList.length, n = secondList.length;
    for (int i = 0, j = 0; i < m && j < n;) {
      int l = Math.max(firstList[i][0], secondList[j][0]);
      int r = Math.min(firstList[i][1], secondList[j][1]);
      if (l <= r) {
        ans.add(new int[]{l, r});
      }
      if (firstList[i][1] < secondList[j][1]) {
        ++i;
      } else {
        ++j;
      }
    }
    return ans.toArray(new int[ans.size()][]);
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> intervalIntersection(vector<vector<int>> &firstList,
                                           vector<vector<int>> &secondList) {
    vector<vector<int>> ans;
    int m = firstList.size(), n = secondList.size();
    for (int i = 0, j = 0; i < m && j < n;) {
      int l = max(firstList[i][0], secondList[j][0]);
      int r = min(firstList[i][1], secondList[j][1]);
      if (l <= r)
        ans.push_back({l, r});
      if (firstList[i][1] < secondList[j][1])
        ++i;
      else
        ++j;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]: i = j = 0 ans = [] while i < len(firstList) and j < len(secondList): s1, e1, s2, e2 = * firstList[i], * secondList[j] l, r = max(s1, s2), min(e1, e2) if l <= r: ans . append([l, r]) if e1 < e2: i += 1 else: j += 1 return ans

```