
### Problem Statement

###### You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [start&#7522;, end&#7522;] and secondList[j] = [start&#11388;, end&#11388;]. 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].

**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] ]**

**Steps To Solve**

- Think of solution without code
  ![Type of Interval](https://assets.leetcode.com/users/arkaung/image_1590249876.png)

  - In every intersection, we have something like End1 >= Start2 and Start1 <= End2. We generalize it in terms of A and B as -

    - Aend >= Bstart and Astart <= Bend

    **Intersection = [Max(Astart, Bstart), Min(Aend, Bend)]**

    ![Overlaps](https://assets.leetcode.com/users/arkaung/image_1590249888.png)

    ![Get overlaps](https://assets.leetcode.com/users/arkaung/image_1590249893.png)

  - Lets take an example :-
    - List1 : **[ [1,3] ,[5,10],[12,17] ]**
    - List2 : **[ [2,4] , [5,7] ,[9,13] ]**
  - Now using our formula we find out the common start point = Max(start1,start2) and common end point = Min(end1,end2) and store these in our array.
  - We see that end1 is less than end2 i.e 3<4 .Thus we know that we cannot use [1,3] for next intersection as it is less than [2,4].So we move to [5,10].
  - Similarly, we calculate for [2,4] and [5,10].We see than common start point = 5 which is greater than common end point = 4. So intersection will not happen. Again we check end points and move pointer in the list which where end point is less. So we move from [2,4] to [5,7] as 4 of [2,4] < 10 of [5,10].

![Incrementing1](https://assets.leetcode.com/users/arkaung/image_1590249920.png)

![Incrementing2](https://assets.leetcode.com/users/arkaung/image_1590249927.png)

![Incrementing3](https://assets.leetcode.com/users/arkaung/image_1590249931.png)

```js
/**
 * @param {number[][]} firstList
 * @param {number[][]} secondList
 * @return {number[][]}
 */
var intervalIntersection = function (firstList, secondList) {
  let ptr1 = 0,
    ptr2 = 0;
  let ans = [];
  while (ptr1 < firstList.length && ptr2 < secondList.length) {
    let commonStart = Math.max(firstList[ptr1][0], secondList[ptr2][0]);
    let commonEnd = Math.min(firstList[ptr1][1], secondList[ptr2][1]);

    if (commonStart <= commonEnd) {
      ans.push([commonStart, commonEnd]);
    }

    if (firstList[ptr1][1] < secondList[ptr2][1]) {
      ptr1++;
    } else {
      ptr2++;
    }
  }

  return ans;
};
```

###### Time and Space Complexity

Time Complexity: **O(M+N)**, where M,N are the lengths of A and B respectively.

Space Complexity: **O(M+N)**, the maximum size of the answer.
