Problem Explanation:

We are given two lists of closed intervals. Each of these lists is sorted and the intervals are pairwise disjoint, meaning each interval does not overlap with any others in the same list. Our goal is to find the intersection of these two lists of intervals.

To understand what an interval is and what an intersection of intervals means, consider the following. An interval [a, b] (where a <= b) represents all the real numbers x such that a <= x <= b. In other words, it represents all the real numbers between a and b, inclusive. For example, interval [2, 5] would represent the numbers 2, 3, 4 and 5. An intersection of two intervals is the set of numbers that both intervals have in common. For example, the intersection of intervals [2, 5] and [4, 6] would be [4, 5] because these are the numbers that are common to both intervals.

Let's take an actual example from the problem statement:

Example:

1
2
3A = [[0,2],[5,10],[13,23],[24,25]]
4B = [[1,5],[8,12],[15,24],[25,26]]

The intersections of the intervals from list A and B would be [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]].

Solution Approach:

To solve this problem, we can iterate through both lists of intervals simultaneously while keeping the indices of our current position in each list.

We will start from the first interval in each list and find the intersection of the two intervals. The start of the intersection would be the maximum of the starts of the two intervals and the end of the intersection would be the minimum of the ends of the two intervals. If the start of the intersection is less than or equal to the end of the intersection, it means the two intervals intersect and we would add the intersection to our result.

Once we have found the intersection of the current intervals, we increment our position in the list which had the smallest end of interval. We do this because we have exhausted all possible intersections involving that interval in that list.

We continue this process while there are remaining intervals in both lists.

C++ Solution:

1
2cpp
3class Solution {
4public:
5  vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
6    vector<vector<int>> ans;
7    int i = 0;
8    int j = 0;
9
10    while (i < firstList.size() && j < secondList.size()) {
11      int lo = max(firstList[i][0], secondList[j][0]);
12      int hi = min(firstList[i][1], secondList[j][1]);
13      
14      // If intersection exists, add it to the result
15      if (lo <= hi)
16        ans.push_back({lo, hi});
17      
18      // Increment the pointer in the list with the smaller end of interval
19      if (firstList[i][1] < secondList[j][1])
20        i++;
21      else
22        j++;
23    }
24
25    return ans;
26  }
27};

In this solution, we first initialize our result set and the iterators i and j to 0.

We then enter the while loop which runs as long as both iterators are within their respective lists' boundaries.

Inside the while loop, we calculate the start and end of the intersection. If there is an intersection (i.e., the start of the intersection is less than or equal to the end), we add it to our result set.

Finally, we increment the iterator of the list which has the smaller end of the current interval, and repeat the loop until we have gone through all the intervals in both lists.

At the end of the loop, we return the result set containing all the intersections.# Python Solution:

The Python solution is similar to the C++ solution in its approach.

1
2python
3def intervalIntersection(firstList, secondList):
4    ans = []
5    i = j = 0
6
7    while i < len(firstList) and j < len(secondList):
8        # Let's check if firstList[i] intersects secondList[j].
9        # lo - the startpoint of the intersection
10        # hi - the endpoint of the intersection
11        lo = max(firstList[i][0], secondList[j][0])
12        hi = min(firstList[i][1], secondList[j][1])
13
14        if lo <= hi:
15            ans.append([lo, hi])
16
17        # Remove the interval with the smallest endpoint.
18        if firstList[i][1] < secondList[j][1]:
19            i += 1
20        else:
21            j += 1
22
23    return ans

JavaScript Solution:

Likewise, the JavaScript solution maintains the same logical approach.

1
2javascript
3var intervalIntersection = function(firstList, secondList) {
4    let res = [];
5    let i = 0, j = 0;
6    
7    while (i < firstList.length && j < secondList.length) {
8        let lo = Math.max(firstList[i][0], secondList[j][0]);
9        let hi = Math.min(firstList[i][1], secondList[j][1]);
10        
11        if (lo <= hi) {
12            res.push([lo, hi]);
13        }
14        
15        if (firstList[i][1] < secondList[j][1]) {
16            i++;
17        } else {
18            j++;
19        }
20    }
21    
22    return res;
23};

Java Solution:

And, finally, the Java solution also follows the exact same line of thought.

1
2java
3class Solution {
4    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
5        List<int[]> ans = new ArrayList();
6        int i = 0, j = 0;
7
8        while (i < firstList.length && j < secondList.length) {
9            int lo = Math.max(firstList[i][0], secondList[j][0]);
10            int hi = Math.min(firstList[i][1], secondList[j][1]);
11
12            if (lo <= hi)
13                ans.add(new int[]{lo, hi});
14
15            if (firstList[i][1] < secondList[j][1])
16                i++;
17            else
18                j++;
19        }
20
21        return ans.toArray(new int[ans.size()][]);
22    }
23}

Wrapping up, this problem gives us a good introduction on how to handle pairwise disjoint and sorted intervals. The concept of using two pointers to navigate through the two lists markedly simplifies the problem and efficiently produces the desired result.