Interval List Intersections

Q: Where would I use this in infra work?

Finding time both of two things were true: when two engineers are both available, when a deploy window overlaps a traffic peak, or when two services were both degraded during an incident. Each side is a sorted list of intervals, and you want their intersection.

Q: Why is it safe to advance the pointer whose interval ends first?

Say first[i] ends first. Every later interval in second starts after second[j] ends, which is at or after first[i] ends. So first[i] cannot intersect any of them, and it can be dropped.

Q: What if both intervals end at the same time?

Advancing either one is correct. Neither interval can intersect anything later in the other list. The code advances j in that case, and the next step will advance i.

mediumIntervals

You get two lists of closed intervals, first and second. Within each list, intervals are sorted and do not overlap each other. A closed interval [a, b] includes both a and b.

Return the intersection of the two lists: every interval of values that is covered by both lists, in sorted order. Two intervals that share just one point, like [4, 6] and [6, 9], intersect in the single-point interval [6, 6].

Examples

Example 1

Input: first = [[1, 4], [6, 9]], second = [[3, 7], [9, 12]]

Output: [[3, 4], [6, 7], [9, 9]]

Explanation: [1, 4] and [3, 7] share [3, 4]; [6, 9] and [3, 7] share [6, 7]; [6, 9] and [9, 12] share only the point 9.

Example 2

Input: first = [[0, 10]], second = [[2, 3], [5, 6], [8, 12]]

Output: [[2, 3], [5, 6], [8, 10]]

Explanation: One long interval intersects each of the three shorter ones.

Hints

Approach

Walk both lists together with two pointers.

Set i = j = 0.
While both pointers are in range:
- compute lo = max(first[i][0], second[j][0]) and hi = min(first[i][1], second[j][1]);
- if lo <= hi, append [lo, hi];
- advance whichever interval ends first (i if first[i][1] < second[j][1], otherwise j). The interval that ends first is fully used up: everything later in the other list starts after it.
Return the result.

Each step advances one pointer, so there are at most m + n steps.

ComplexityTime O(m + n)Space O(1) extra

Python

class Solution:
    def intervalIntersection(self, first: list[list[int]], second: list[list[int]]) -> list[list[int]]:
        out = []
        i = j = 0
        while i < len(first) and j < len(second):
            lo = max(first[i][0], second[j][0])
            hi = min(first[i][1], second[j][1])
            if lo <= hi:
                out.append([lo, hi])
            if first[i][1] < second[j][1]:
                i += 1
            else:
                j += 1
        return out

Follow-up questions

Return the union of the two lists instead of the intersection.
Intersect k sorted interval lists at once.

Frequently asked questions

Finding time both of two things were true: when two engineers are both available, when a deploy window overlaps a traffic peak, or when two services were both degraded during an incident. Each side is a sorted list of intervals, and you want their intersection.

Say first[i] ends first. Every later interval in second starts after second[j] ends, which is at or after first[i] ends. So first[i] cannot intersect any of them, and it can be dropped.

Advancing either one is correct. Neither interval can intersect anything later in the other list. The code advances j in that case, and the next step will advance i.

Problem statement