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 &lt;= b) denotes the set of real numbers x with a &lt;= x &lt;= 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].

&nbsp;
Example 1:

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: []


&nbsp;
Constraints:


	0 &lt;= firstList.length, secondList.length &lt;= 1000
	firstList.length + secondList.length &gt;= 1
	0 &lt;= starti &lt; endi &lt;= 109
	endi &lt; starti+1
	0 &lt;= startj &lt; endj &lt;= 109 
	endj &lt; startj+1


from collections import deque

class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:

        answer = []

        if len(firstList) == 0 or len(secondList) == 0:
            return answer

        first_queue= deque(firstList)
        second_queue = deque(secondList )

        first = first_queue.popleft()
        second = second_queue.popleft()

        while first_queue or second_queue:

            if first[1] < second[0]:
                if len(first_queue):
                    first = first_queue.popleft()
                    continue
                break
            if second[1] < first[0]:
                if len(second_queue) > 0:
                    second = second_queue.popleft()
                    continue
                break

            if first[0] <= second[0] and second[0] <= first[1]:
                if first[1] <= second[1]:
                    answer.append([second[0], first[1]])
                    if len(first_queue) > 0:
                        first = first_queue.popleft()
                        continue
                    break

                else:
                    answer.append(second)
                    if len(second_queue) > 0:
                        second = second_queue.popleft()
                        continue
                    break
            if second[0] <= first[0] and first[0] <= second[1]:
                if second[1] <= first[1]:
                    answer.append([first[0], second[1]])
                    if len(second_queue) > 0:
                        second = second_queue.popleft()
                        continue
                    break

                else:
                    answer.append(first)
                    if len(first_queue) > 0:
                        first = first_queue.popleft()
                        continue
                    break

        if first[0] <= second[0] and second[0] <= first[1]:
            if first[1] <= second[1]:

                if len(answer) > 0:

                    if answer[-1] != [second[0], first[1]]:
                        answer.append([second[0], first[1]])
                elif not answer:
                    answer.append([second[0], first[1]])
            else:
                if len(answer) > 0:
                    if answer[-1] != second:
                        answer.append(second)
                elif not answer:
                    answer.append(second)
        elif second[0] <= first[0] and first[0] <= second[1]:
            if second[1] <= first[1]:
                if len(answer) > 0:
                    if answer[-1] != [first[0], second[1]]:
                        answer.append([first[0], second[1]])
                elif not answer:
                    answer.append([first[0], second[1]])
            else:
                if len(answer) > 0:
                    if answer[-1] != first:
                        answer.append(first)
                elif not answer:

                    answer.append(first)

        return answer
class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        int i = 0;
        int j = 0;
        
        List<int[]> ans = new ArrayList<>();
        
        while(i<firstList.length && j<secondList.length){
            int a[] = firstList[i];
            int b[] = secondList[j];
            
            if(b[0]<=a[1] && b[0]>=a[0])
                ans.add(new int[]{b[0], Math.min(a[1], b[1])});
            else if(a[0]<=b[1] && a[0]>=b[0])
                ans.add(new int[]{a[0], Math.min(a[1], b[1])});
            
            if(a[1]<=b[1])
                i++;
            else
                j++;
        }
        
        int res[][] = new int[ans.size()][2];
        
        for(i=0;i<ans.size();i++){
            res[i] = ans.get(i);
        }
        return res;
    }
}
class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
        vector<vector<int>> result;
        int i = 0;
        int j = 0;
        while(i < firstList.size() && j < secondList.size()){
            if((firstList[i][0] >= secondList[j][0] && firstList[i][0] <= secondList[j][1])||(secondList[j][0] >= firstList[i][0] && secondList[j][0] <= firstList[i][1]) ){
                //there is an overlap
                result.push_back( {max(firstList[i][0], secondList[j][0]), min(firstList[i][1], secondList[j][1])});
            }
            if(firstList[i][1] < secondList[j][1]){
                i++;
            }
            else{
                j++;
            }
        }
        return result;
    }
};
var intervalIntersection = function(firstList, secondList) {
    //if a overlap b - a.start >= b.start && a.start <= b.end
    //if b overlap a - b.start >= a.start && b.start <= a.end

    //handle empty edge cases
    if(firstList.length === 0 || secondList.length === 0){
        return [];
    }

    let merged = [];
    let i =0;
    let j = 0;
    while(i<firstList.length && j < secondList.length){
        let a_overlap_b = firstList[i][0] >= secondList[j][0] && firstList[i][0] <= secondList[j][1];
        let b_overlap_a = secondList[j][0] >= firstList[i][0] && secondList[j][0] <= firstList[i][1];

        if(a_overlap_b || b_overlap_a){
            let start = Math.max(firstList[i][0], secondList[j][0]);
            let end = Math.min(firstList[i][1], secondList[j][1]);
            merged.push([start, end]);
        }

        if(firstList[i][1] < secondList[j][1]){
            i++;
        }else {
            j++;
        }
    }

    return merged;

};
Interval List Intersections