Interval List Intersections

📋

Problem

Imagine two friends each have their own schedule of busy time slots, and you want to find all the times when both are busy simultaneously.

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists. Each intersection is a closed interval that represents the overlapping time between intervals from the two lists.

1 ≤ number of intervals in each list ≤ 10^5Intervals are sorted by start time and do not overlap within the same listInterval start and end values are integers within a valid range

Edge cases: One or both lists are empty → output is empty listIntervals that touch at a single point (e.g., [1,2] and [2,3]) → intersection is that single point [2,2]One list has intervals completely before or after the other list → no intersections

</>

IDE

def intervalIntersection(A: list[list[int]], B: list[list[int]]) -> list[list[int]]:public List<int[]> intervalIntersection(List<int[]> A, List<int[]> B)vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B)function intervalIntersection(A, B)

def intervalIntersection(A, B):
    # Write your solution here
    pass

class Solution {
    public List<int[]> intervalIntersection(List<int[]> A, List<int[]> B) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
    // Write your solution here
    return {};
}

function intervalIntersection(A, B) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[1,5],[8,10],[15,24],[25,25]]Incorrectly adding intervals from one list without intersecting with the other; missing partial overlaps.✅ Compute intersection as [max(startA, startB), min(endA, endB)] only if max start <= min end, and advance pointer of interval with smaller end.

Wrong: [[2,2]]Missing single-point intersections due to strict inequality in overlap check.✅ Use <= in overlap condition: if max(startA, startB) <= min(endA, endB), add intersection.

Wrong: [[1,2],[3,4],[5,6],[1,10]]Treating intervals as unbounded or not advancing pointers properly, causing duplicates or incorrect intervals.✅ Advance pointer of interval with smaller end after processing intersection; do not add intervals without intersection.

Wrong: Timeout or no outputUsing brute force nested loops O(m*n) for large inputs.✅ Implement two-pointer approach with O(m+n) time complexity.

✓

Test Cases

Focus on handling empty and minimal inputs correctly before moving on.

Review pointer advancement logic and overlap conditions to avoid common pitfalls.

Optimize your solution to linear time using two pointers to handle large inputs.

t1_01basic

Input{"A":[[0,2],[5,10],[13,23],[24,25]],"B":[[1,5],[8,12],[15,24],[25,26]]}

Expected[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

⏱ Performance - must finish in 2000ms

We find all overlapping intervals by comparing intervals from A and B and collecting their intersections.

💡 Use two pointers to traverse both interval lists simultaneously.

💡 At each step, find the max start and min end to detect overlap.

💡 Advance the pointer of the interval that ends first to find all intersections.

Why it failed: Incorrect intersections due to wrong pointer advancement or overlap calculation. Fix by advancing pointer of interval with smaller end and computing intersection as [max(startA, startB), min(endA, endB)] only if max start <= min end.

✓ Correct intersections found using two-pointer approach.

t1_02basic

Input{"A":[[1,3],[5,9]],"B":[[2,5],[7,10]]}

Expected[[2,3],[5,5],[7,9]]

⏱ Performance - must finish in 2000ms

Intersections are [2,3] from [1,3] and [2,5], [5,5] from [5,9] and [2,5], and [7,9] from [5,9] and [7,10].

💡 Check each pair of intervals for overlap using max start and min end.

💡 Remember to move the pointer of the interval that ends first after processing.

💡 Ensure to add intersection only if max start <= min end.

Why it failed: Missed intersections or incorrect intervals due to not advancing pointers correctly or incorrect overlap condition. Fix by advancing pointer of interval with smaller end and checking overlap with max start <= min end.

✓ All intersections correctly identified with proper pointer movement.

t2_01edge

Input{"A":[],"B":[[1,3],[5,7]]}

Expected[]

⏱ Performance - must finish in 2000ms

One list is empty, so no intersections exist.

💡 Check for empty input lists before processing.

💡 If either list is empty, the result must be empty.

💡 Return empty list immediately if any input list is empty.

Why it failed: Code fails to handle empty input lists, producing non-empty or error output. Fix by adding checks to return empty list if either input is empty.

✓ Correctly returns empty list when one input list is empty.

t2_02edge

Input{"A":[[2,2]],"B":[[2,2]]}

Expected[[2,2]]

⏱ Performance - must finish in 2000ms

Single-point intervals intersect exactly at [2,2].

💡 Handle intervals where start == end as valid intervals.

💡 Overlap occurs if max start <= min end, including equality.

💡 Include single-point intersections when intervals touch at a point.

Why it failed: Fails to detect single-point intersections due to strict inequality. Fix by using <= in overlap condition.

✓ Correctly detects single-point intersections.

t2_03edge

Input{"A":[[1,2],[3,4]],"B":[[5,6],[7,8]]}

Expected[]

⏱ Performance - must finish in 2000ms

Intervals in B are completely after intervals in A, so no intersections.

💡 Check if intervals do not overlap when one ends before the other starts.

💡 Advance pointers correctly when intervals do not overlap.

💡 Return empty list if no overlaps found after full traversal.

Why it failed: Incorrectly returns intersections when intervals do not overlap. Fix by checking max start <= min end before adding intersection.

✓ Correctly returns empty list when no intervals overlap.

t3_01corner

Input{"A":[[1,5],[10,14],[16,18]],"B":[[2,6],[8,10],[11,20]]}

Expected[[2,5],[10,10],[11,14],[16,18]]

⏱ Performance - must finish in 2000ms

Tests correct handling of multiple overlapping intervals and pointer advancement.

💡 Beware of greedy approach that always advances pointer of A or B without comparing ends.

💡 Use two-pointer technique advancing pointer with smaller interval end.

💡 Calculate intersection as [max starts, min ends] and advance pointer with smaller end.

Why it failed: Greedy pointer advancement ignoring interval ends causes missed intersections. Fix by advancing pointer of interval with smaller end after processing intersection.

✓ Correctly handles multiple overlapping intervals with proper pointer advancement.

t3_02corner

Input{"A":[[1,3],[5,7],[9,11]],"B":[[2,4],[6,8],[10,12]]}

Expected[[2,3],[6,7],[10,11]]

⏱ Performance - must finish in 2000ms

Tests correct intersection detection when intervals partially overlap and are interleaved.

💡 Check overlap condition carefully for each pair.

💡 Advance pointer of interval with smaller end to avoid missing intersections.

💡 Do not assume intervals are aligned; handle partial overlaps correctly.

Why it failed: Incorrect overlap detection or pointer advancement causes missing intersections. Fix by checking max start <= min end and advancing pointer with smaller end.

✓ Correctly detects all partial overlaps with proper pointer logic.

t3_03corner

Input{"A":[[1,2],[3,4],[5,6]],"B":[[1,10]]}

Expected[[1,2],[3,4],[5,6]]

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 and unbounded intervals; B covers all A intervals.

💡 Do not treat intervals as unbounded; respect their start and end.

💡 Check intersection as max start and min end for each pair.

💡 Advance pointer of interval with smaller end after processing.

Why it failed: Treating intervals as unbounded causes incorrect intersections or missing some. Fix by using exact interval boundaries and advancing pointers properly.

✓ Correctly handles intervals fully contained within another.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 tests O(m+n) two-pointer solution performance within 2 seconds.

💡 Brute force O(m*n) will time out for large inputs.

💡 Use two-pointer approach with O(m+n) time complexity.

💡 Advance pointer of interval with smaller end to achieve linear time.

Why it failed: Solution times out due to O(m*n) brute force complexity. Fix by implementing two-pointer linear time algorithm.

✓ Solution runs efficiently in O(m+n) time for large inputs.

Practice

1. Consider the following Python function that returns the maximum number of non-overlapping intervals. What is the value of the variable removals after the second iteration of the loop when the input is [[1,3],[2,4],[3,5]]?

from typing import List

def max_non_overlapping_intervals(intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda x: x[0])
    removals = 0
    last_end = intervals[0][1]
    for i in range(1, len(intervals)):
        if intervals[i][0] < last_end:
            removals += 1
            last_end = min(last_end, intervals[i][1])
        else:
            last_end = intervals[i][1]
    return len(intervals) - removals

intervals = [[1,3],[2,4],[3,5]]
print(max_non_overlapping_intervals(intervals))

easy

A. 1

B. 3

C. 2

D. 0

Solution

1. Step 1: Trace first iteration (i=1)

   Intervals sorted by start: [[1,3],[2,4],[3,5]]. last_end=3. At i=1, intervals[1][0]=2 < 3, so removals=1, last_end=min(3,4)=3.

2. Step 2: Trace second iteration (i=2)

   At i=2, intervals[2][0]=3 <= last_end=3 is false, so last_end=5, removals remains 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   removals incremented once at i=1 only [OK]

Hint: Check overlap condition carefully at each iteration [OK]

Common Mistakes:

• Off-by-one error in loop iteration
• Misunderstanding when to increment removals
• Confusing last_end update logic

2. What is the time complexity of the optimal car pooling solution using the difference array and prefix sum approach, given n trips and maximum location L?

medium

A. O(n * L) because we must simulate passenger count at every location for each trip

B. O(n + L) because we process each trip once and then sweep through the difference array once

C. O(n log n) due to sorting trips by start location before processing

D. O(L) because the difference array size dominates and trips are processed in constant time

Solution

1. Step 1: Analyze trip processing

   Each of the n trips updates two positions in the difference array -> O(n)

2. Step 2: Analyze prefix sum sweep

   We iterate over the difference array of size L once -> O(L)

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum of O(n) + O(L) operations [OK]

Hint: Difference array updates O(n), prefix sum O(L) [OK]

Common Mistakes:

• Confusing brute force O(n*L) with optimal
• Assuming sorting is required
• Ignoring prefix sum sweep cost

3. The following code attempts to implement the optimal car pooling solution. Which line contains a subtle bug that can cause incorrect capacity checks?

def carPooling(trips, capacity):
    max_location = 0
    for _, start, end in trips:
        max_location = max(max_location, end)
    diff = [0] * (max_location + 1)
    for num, start, end in trips:
        diff[start] += num
        diff[end] += num  # Bug here
    current_passengers = 0
    for i in range(max_location + 1):
        current_passengers += diff[i]
        if current_passengers > capacity:
            return false
    return true

medium

A. Line that increments diff[end] by num instead of decrementing

B. Line that updates max_location in the first loop

C. Line that increments diff[start] by num

D. Line that checks if current_passengers exceeds capacity

Solution

1. Step 1: Understand difference array updates

   Passengers boarding at start location increase count; passengers leaving at end location must decrease count.

2. Step 2: Identify incorrect update

   Line incrementing diff[end] by num adds passengers instead of removing them, causing incorrect capacity calculation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Increment at end location breaks capacity tracking [OK]

Hint: End location must decrement passengers, not increment [OK]

Common Mistakes:

• Incrementing instead of decrementing at end
• Forgetting to update difference array
• Checking capacity before summing passengers

4. What is the time complexity of the optimal min-heap approach for the Meeting Rooms II problem, given n intervals? Beware of common misconceptions about sorting and heap operations.

medium

A. O(n log k) where k is the number of rooms, but k can be up to n, so effectively O(n log n).

B. O(n^2) because each interval may be compared with all others.

C. O(n log n) due to sorting and heap operations for each interval.

D. O(n) because heap operations are constant time on average.

Solution

1. Step 1: Identify sorting cost.

   Sorting intervals by start time costs O(n log n).

2. Step 2: Analyze heap operations.

   Each interval is pushed and possibly popped from a min-heap of size k (number of rooms). Each heap operation costs O(log k).

3. Step 3: Combine complexities.

   Total heap operations are O(n log k). Since k ≤ n, worst case is O(n log n).

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Sorting + heap operations dominate; heap size bounded by n [OK]

Hint: Heap ops depend on number of rooms k, bounded by n [OK]

Common Mistakes:

• Assuming heap ops are O(1)
• Confusing n and k in complexity
• Thinking sorting is O(n)

5. Examine the following code snippet intended to compute the minimum number of platforms required. Identify the line containing the subtle bug that can cause incorrect platform count when a train departs and another arrives at the same time.

medium

A. Line 6: Appending departure events with -1 instead of 1

B. Line 10: Not resetting platforms_needed before loop

C. Line 8: Sorting events with arrival before departure on tie

D. Line 12: Not updating max_platforms after each event

Solution

1. Step 1: Understand event sorting importance

   When arrival and departure times are equal, departures must be processed before arrivals to free platforms.

2. Step 2: Identify sorting key bug

   The code sorts with arrival (1) before departure (-1) on tie, causing overcounting platforms.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Departure before arrival on tie avoids overcounting [OK]

Hint: Departure events must come before arrival on tie [OK]

Common Mistakes:

• Sorting arrival before departure on tie
• Forgetting to update max_platforms
• Incorrect event type values