986. Interval List Intersections

You are given two lists of closed intervals, firstList and secondList, where $firstList[i]=[star{t}_i,en{d}_i]$ and $secondList[j]=[star{t}_j,en{d}_j]$. 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:

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<=star{t}_i<en{d}_i<=10^9$
• $en{d}_i<star{t}_{i+1}$
• $0<=star{t}_j<en{d}_j<=10^9$
• $en{d}_j<star{t}_{j+1}$

From: LeetCode
Link: 986. Interval List Intersections

Solution:

Ideas:

• Use two pointers, one for each interval list.

• Since lists are sorted and disjoint, scan them only once.

• For current intervals:

  • Intersection start = max(start1, start2)
  • Intersection end = min(end1, end2)

• If start <= end, the intervals overlap → add this range to the answer.

• Move forward the pointer of the interval that ends first.

• Continue until one list is fully processed.

Code:

static inline int max2(int a, int b) { return a > b ? a : b; }
static inline int min2(int a, int b) { return a < b ? a : b; }

int** intervalIntersection(
    int** firstList, int firstListSize, int* firstListColSize,
    int** secondList, int secondListSize, int* secondListColSize,
    int* returnSize, int** returnColumnSizes
) {
    (void)firstListColSize;   // always 2 per problem statement
    (void)secondListColSize;  // always 2 per problem statement

    *returnSize = 0;

    // If one list is empty, answer is empty
    if (firstListSize == 0 || secondListSize == 0) {
        *returnColumnSizes = NULL;
        return NULL;
    }

    // Max possible intersections is at most firstListSize + secondListSize
    int cap = firstListSize + secondListSize;
    int** res = (int**)malloc(sizeof(int*) * cap);
    int* colSizes = (int*)malloc(sizeof(int) * cap);

    int i = 0, j = 0;

    while (i < firstListSize && j < secondListSize) {
        int aStart = firstList[i][0], aEnd = firstList[i][1];
        int bStart = secondList[j][0], bEnd = secondList[j][1];

        int start = max2(aStart, bStart);
        int end   = min2(aEnd, bEnd);

        if (start <= end) {
            int* pair = (int*)malloc(sizeof(int) * 2);
            pair[0] = start;
            pair[1] = end;
            res[*returnSize] = pair;
            colSizes[*returnSize] = 2;
            (*returnSize)++;
        }

        // Move the one that ends first
        if (aEnd < bEnd) i++;
        else j++;
    }

    // Optional: shrink to actual size
    if (*returnSize == 0) {
        free(res);
        free(colSizes);
        *returnColumnSizes = NULL;
        return NULL;
    }

    res = (int**)realloc(res, sizeof(int*) * (*returnSize));
    colSizes = (int*)realloc(colSizes, sizeof(int) * (*returnSize));

    *returnColumnSizes = colSizes;
    return res;
}