Interval List Intersections

Given two lists of closed intervals, firstList and secondList, where firstList[i] = [start_i, end_i] and secondList[j] = [start_j, end_j], find the intersection of these two lists.

An intersection is a closed interval that represents the overlap between two intervals. If there is no intersection, the result should be an empty list.

Example:

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

Explanation: In the input, the intersection of firstList and secondList is [1, 2], [5, 5], [8, 10], [15, 23], [24, 24], and [25, 25].

Interval List Intersections Solution in C++:

#include <iostream>
#include <vector>

// Function to find the intersection of two interval lists
std::vector<std::vector<int>> intervalIntersection(std::vector<std::vector<int>>& firstList, std::vector<std::vector<int>>& secondList) {
    std::vector<std::vector<int>> result;
    int i = 0;
    int j = 0;

    // Iterate through the first and second interval lists
    while (i < firstList.size() && j < secondList.size()) {
        int start1 = firstList[i][0];
        int end1 = firstList[i][1];
        int start2 = secondList[j][0];
        int end2 = secondList[j][1];

        // Check for intersection between the two intervals
        if (end1 >= start2 && end2 >= start1) {
            // Compute the intersection interval [max(start1, start2), min(end1, end2)]
            result.push_back({std::max(start1, start2), std::min(end1, end2)});
        }

        // Move the pointer for the interval that ends first
        if (end1 < end2) {
            ++i;
        } else {
            ++j;
        }
    }

    return result;
}

int main() {
    std::vector<std::vector<int>> firstList = {{0, 2}, {5, 10}, {13, 23}, {24, 25}};
    std::vector<std::vector<int>> secondList = {{1, 5}, {8, 12}, {15, 24}, {25, 26}};

    std::vector<std::vector<int>> result = intervalIntersection(firstList, secondList);

    std::cout << "Intersection Intervals:\n";
    for (const auto& interval : result) {
        std::cout << "[" << interval[0] << ", " << interval[1] << "] ";
    }
    std::cout << std::endl;

    return 0;
}

Explanation:

1. The intervalIntersection function takes references to two vectors of vectors, firstList and secondList.
2. We create a new vector result to store the intersection intervals.
3. We initialize two pointers, i and j, to 0, representing the current index for firstList and secondList, respectively.
4. We use a while loop to iterate through both lists simultaneously.
5. For each pair of intervals, [start1, end1] from firstList, and [start2, end2] from secondList, we check for an intersection. An intersection exists if end1 >= start2 and end2 >= start1.
6. If an intersection is found, we compute the intersection interval as [max(start1, start2), min(end1, end2)] and add it to the result vector.
7. After processing the current intervals, we move the pointer of the interval that ends first. This helps us progress through both lists efficiently.

Time Complexity:

The time complexity of this solution is O(m + n), where m is the size of firstList and n is the size of secondList. The while loop iterates through both lists once, and each iteration takes constant time.

Space Complexity:

The space complexity of this solution is O(1) for the result vector, as we are not using any additional data structures that grow with the input size.