Interval List Intersections

LeetCode 986: Interval List Intersections Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses a greedy line sweep approach via two pointers to find overlapping regions by strictly advancing the interval that ends first.

In this problem, you are given two lists of closed intervals, firstList and secondList. Each individual list is sorted by start time and contains entirely disjoint (non-overlapping) intervals. The goal is to return a new list representing the exact intersections between the intervals of the two lists.

Finding the overlaps between distinct datasets is a popular interview question. Mastering the LeetCode 986 Solution requires leveraging the pre-sorted nature of the arrays to find intersections efficiently without redundant comparisons.

Brute Force Approach for Interval List Intersections

The most intuitive but naive way to solve Interval List Intersections is to compare every interval in firstList against every interval in secondList to check for an overlap.

Initialize an empty list 'result'
For each interval 'A' in firstList:
    For each interval 'B' in secondList:
        start = max(A.start, B.start)
        end = min(A.end, B.end)
        if start <= end:
            add [start, end] to 'result'
Return 'result'

Complexity Analysis of Brute Force

• Time Complexity: $O(N \times M)$, where $N$ is the length of firstList and $M$ is the length of secondList. Every interval is compared against every other interval.
• Space Complexity: $O(1)$ auxiliary space.

Why it Fails

While $O(N \times M)$ might barely pass the time limits for small constraints ($1000 \times 1000 = 10^6$ operations), it is considered suboptimal in an interview setting. The brute force approach completely ignores the fact that both lists are already sorted and internally disjoint. Once an interval in secondList is entirely ahead of an interval in firstList, continuing to iterate through the inner loop is a waste of computational resources.

Algorithm Strategy: Greedy Patterns

To implement the optimized Line Sweep, we maintain two pointers, one for each list. These pointers act as our sweep line, tracking the currently "active" interval in both lists.

At each step, we calculate the potential overlap. If the computed start time is less than or equal to the computed end time, an intersection exists, and we record it.

Next, we must decide which interval to discard (sweep past). We make a greedy choice: we compare the end times of the two currently active intervals. The interval with the smaller end time is exhausted—it can no longer intersect with any upcoming intervals. We increment the pointer for that list, effectively moving the sweep line forward. This process repeats until we exhaust all intervals in either list.

Execution Flow

1. Initialize two pointers, i = 0 and j = 0, representing the current intervals in firstList and secondList.
2. Initialize an empty dynamic array result to store the intersections.
3. Loop while i < firstList.length and j < secondList.length:
4. Calculate the start of the potential intersection: overlap_start = max(firstList[i][0], secondList[j][0]).
5. Calculate the end of the potential intersection: overlap_end = min(firstList[i][1], secondList[j][1]).
6. If overlap_start <= overlap_end, a valid overlap exists. Append [overlap_start, overlap_end] to result.
7. Greedily advance the sweep line:
   • If firstList[i][1] < secondList[j][1], the interval in firstList ends first. Increment i.
   • Otherwise, the interval in secondList ends first (or they end at the same time). Increment j.
8. Return the result array.

Proof of Correctness

The algorithm correctly identifies all overlaps because it exhaustively checks the intersection of the only two intervals that could possibly overlap at any given point on the timeline.

By defining the overlap as [max(start1, start2), min(end1, end2)], we mathematically isolate the shared region. Furthermore, discarding the interval with the smaller end time ensures no valid overlaps are skipped. If firstList[i] ends before secondList[j], firstList[i] cannot overlap with secondList[j+1] because secondList[j+1] must start after secondList[j] ends (due to the sorted, disjoint properties). Thus, the greedy pointer advancement is safe and maintains the invariant.

Pattern Reuse Notes

The Greedy Line Sweep pattern is highly versatile and frequently appears in interval-based coordinate geometry problems. The following problems share the same pattern/subpattern:

• LeetCode 759: Employee Free Time

In "Employee Free Time", the same Line Sweep logic applies. Instead of finding overlapping active regions, the sweep line processes sorted interval boundaries to identify gaps where the active interval count drops to zero, perfectly mirroring the event-driven timeline logic used here.

Reference Implementation

C++ Solution for LeetCode 986

1#include <vector>
2#include <algorithm>
3
4using namespace std;
5
6class Solution {
7public:
8    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
9        vector<vector<int>> result;
10        int i = 0;
11        int j = 0;
12        
13        while (i < firstList.size() && j < secondList.size()) {
14            // Calculate potential intersection boundaries
15            int overlap_start = max(firstList[i][0], secondList[j][0]);
16            int overlap_end = min(firstList[i][1], secondList[j][1]);
17            
18            // Check if boundaries form a valid closed interval
19            if (overlap_start <= overlap_end) {
20                result.push_back({overlap_start, overlap_end});
21            }
22            
23            // Greedily advance the sweep line based on the earliest end time
24            if (firstList[i][1] < secondList[j][1]) {
25                i++;
26            } else {
27                j++;
28            }
29        }
30        
31        return result;
32    }
33};

Java Solution for LeetCode 986

1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
6        List<int[]> result = new ArrayList<>();
7        int i = 0;
8        int j = 0;
9        
10        while (i < firstList.length && j < secondList.length) {
11            // Calculate potential intersection boundaries
12            int overlapStart = Math.max(firstList[i][0], secondList[j][0]);
13            int overlapEnd = Math.min(firstList[i][1], secondList[j][1]);
14            
15            // Check if boundaries form a valid closed interval
16            if (overlapStart <= overlapEnd) {
17                result.add(new int[]{overlapStart, overlapEnd});
18            }
19            
20            // Greedily advance the sweep line based on the earliest end time
21            if (firstList[i][1] < secondList[j][1]) {
22                i++;
23            } else {
24                j++;
25            }
26        }
27        
28        return result.toArray(new int[result.size()][]);
29    }
30}

Python Solution for LeetCode 986

1from typing import List
2
3class Solution:
4    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
5        result = []
6        i, j = 0, 0
7        
8        while i < len(firstList) and j < len(secondList):
9            # Calculate potential intersection boundaries
10            overlap_start = max(firstList[i][0], secondList[j][0])
11            overlap_end = min(firstList[i][1], secondList[j][1])
12            
13            # Check if boundaries form a valid closed interval
14            if overlap_start <= overlap_end:
15                result.append([overlap_start, overlap_end])
16                
17            # Greedily advance the sweep line based on the earliest end time
18            if firstList[i][1] < secondList[j][1]:
19                i += 1
20            else:
21                j += 1
22                
23        return result