Interval List Intersections

▶

Steps

setup

Initialize pointers and result

Set pointers i and j to 0 to start at the beginning of arrays A and B. Initialize an empty result list to store intersections.

💡 Starting both pointers at zero ensures we compare intervals from the start of both lists.

Line:

i, j = 0, 0
result = []

💡 We begin with the first intervals in both lists to find any initial overlaps.

compare

Compare A[i] and B[j] for overlap

Check if intervals A[0] = [0,2] and B[0] = [1,5] overlap by comparing their start and end points.

💡 Determining overlap is key to deciding whether to record an intersection or move pointers.

Line:

if A[i][1] < B[j][0]:
    i += 1
elif B[j][1] < A[i][0]:
    j += 1
else:

💡 Intervals overlap if the end of one is not less than the start of the other.

insert

Record intersection of A[0] and B[0]

Calculate intersection start as max(0,1)=1 and end as min(2,5)=2, then append [1,2] to result.

💡 Recording the intersection captures the overlapping portion of the intervals.

Line:

start = max(A[i][0], B[j][0])
end = min(A[i][1], B[j][1])
result.append([start, end])

💡 The intersection is the overlapping range between the two intervals.

shrink

Advance pointer with smaller interval end

Since A[0].end=2 < B[0].end=5, increment i to 1 to check next interval in A.

💡 Advancing the pointer with smaller end avoids missing future overlaps.

Line:

if A[i][1] < B[j][1]:
    i += 1
else:
    j += 1

💡 Moving the pointer with smaller end ensures all overlaps are found efficiently.

compare

Compare A[1] and B[0] for overlap

Check if A[1] = [5,10] and B[0] = [1,5] overlap by comparing their intervals.

💡 Each comparison determines if intervals intersect or if pointers should move.

Line:

if A[i][1] < B[j][0]:
    i += 1
elif B[j][1] < A[i][0]:
    j += 1
else:

💡 Intervals that touch at a point (end == start) are considered overlapping.

insert

Record intersection of A[1] and B[0]

Calculate intersection start=max(5,1)=5 and end=min(10,5)=5, append [5,5] to result.

💡 Even a single point overlap is recorded as an intersection interval.

Line:

start = max(A[i][0], B[j][0])
end = min(A[i][1], B[j][1])
result.append([start, end])

💡 Intersections can be zero-length intervals representing a single point.

shrink

Advance pointer with smaller interval end

Since B[0].end=5 < A[1].end=10, increment j to 1 to check next interval in B.

💡 Moving the pointer with smaller end keeps the search efficient.

Line:

if A[i][1] < B[j][1]:
    i += 1
else:
    j += 1

💡 Advancing the pointer with smaller end avoids missing overlaps.

compare

Compare A[1] and B[1] for overlap

Check if A[1] = [5,10] and B[1] = [8,12] overlap by comparing their intervals.

💡 Each comparison checks if intervals intersect or if pointers should move.

Line:

if A[i][1] < B[j][0]:
    i += 1
elif B[j][1] < A[i][0]:
    j += 1
else:

💡 Intervals overlap if their ranges intersect.

insert

Record intersection of A[1] and B[1]

Calculate intersection start=max(5,8)=8 and end=min(10,12)=10, append [8,10] to result.

💡 Recording the overlapping portion adds to the final answer.

Line:

start = max(A[i][0], B[j][0])
end = min(A[i][1], B[j][1])
result.append([start, end])

💡 The intersection is the overlapping range between the two intervals.

shrink

Advance pointer with smaller interval end

Since A[1].end=10 < B[1].end=12, increment i to 2 to check next interval in A.

💡 Advancing the pointer with smaller end keeps the search efficient.

Line:

if A[i][1] < B[j][1]:
    i += 1
else:
    j += 1

💡 Moving the pointer with smaller end ensures all overlaps are found.

compare

Compare A[2] and B[1] for overlap

Check if A[2] = [13,23] and B[1] = [8,12] overlap by comparing their intervals.

💡 Each comparison checks if intervals intersect or if pointers should move.

Line:

if A[i][1] < B[j][0]:
    i += 1
elif B[j][1] < A[i][0]:
    j += 1
else:

💡 If one interval ends before the other starts, no overlap exists.

move_right

Advance pointer j to skip B[1]

Since B[1] ends before A[2] starts, increment j to 2 to check next interval in B.

💡 Skipping intervals that cannot overlap improves efficiency.

Line:

elif B[j][1] < A[i][0]:
    j += 1

💡 Moving pointer j skips intervals that end before current A[i] starts.

compare

Compare A[2] and B[2] for overlap

Check if A[2] = [13,23] and B[2] = [15,24] overlap by comparing their intervals.

💡 Each comparison checks if intervals intersect or if pointers should move.

Line:

if A[i][1] < B[j][0]:
    i += 1
elif B[j][1] < A[i][0]:
    j += 1
else:

💡 Intervals overlap if their ranges intersect.

insert

Record intersection of A[2] and B[2]

Calculate intersection start=max(13,15)=15 and end=min(23,24)=23, append [15,23] to result.

💡 Recording the overlapping portion adds to the final answer.

Line:

start = max(A[i][0], B[j][0])
end = min(A[i][1], B[j][1])
result.append([start, end])

💡 The intersection is the overlapping range between the two intervals.

shrink

Advance pointer with smaller interval end

Since A[2].end=23 < B[2].end=24, increment i to 3 to check next interval in A.

💡 Advancing the pointer with smaller end keeps the search efficient.

Line:

if A[i][1] < B[j][1]:
    i += 1
else:
    j += 1

💡 Moving the pointer with smaller end ensures all overlaps are found.

compare

Compare A[3] and B[2] for overlap

Check if A[3] = [24,25] and B[2] = [15,24] overlap by comparing their intervals.

💡 Each comparison checks if intervals intersect or if pointers should move.

Line:

if A[i][1] < B[j][0]:
    i += 1
elif B[j][1] < A[i][0]:
    j += 1
else:

💡 Intervals that touch at a point (end == start) are considered overlapping.

insert

Record intersection of A[3] and B[2]

Calculate intersection start=max(24,15)=24 and end=min(25,24)=24, append [24,24] to result.

💡 Recording the overlapping portion adds to the final answer.

Line:

start = max(A[i][0], B[j][0])
end = min(A[i][1], B[j][1])
result.append([start, end])

💡 The intersection is the overlapping range between the two intervals.

shrink

Advance pointer with smaller interval end

Since B[2].end=24 < A[3].end=25, increment j to 3 to check next interval in B.

💡 Advancing the pointer with smaller end keeps the search efficient.

Line:

if A[i][1] < B[j][1]:
    i += 1
else:
    j += 1

💡 Moving the pointer with smaller end ensures all overlaps are found.

compare

Compare A[3] and B[3] for overlap

Check if A[3] = [24,25] and B[3] = [25,26] overlap by comparing their intervals.

💡 Each comparison checks if intervals intersect or if pointers should move.

Line:

if A[i][1] < B[j][0]:
    i += 1
elif B[j][1] < A[i][0]:
    j += 1
else:

💡 Intervals that touch at a point (end == start) are considered overlapping.

insert

Record intersection of A[3] and B[3]

Calculate intersection start=max(24,25)=25 and end=min(25,26)=25, append [25,25] to result.

💡 Recording the overlapping portion adds to the final answer.

Line:

start = max(A[i][0], B[j][0])
end = min(A[i][1], B[j][1])
result.append([start, end])

💡 The intersection is the overlapping range between the two intervals.

shrink

Advance pointer with smaller interval end

Since A[3].end=25 < B[3].end=26, increment i to 4, which ends the loop as i >= len(A).

💡 Advancing pointer i ends the traversal since all intervals in A are processed.

Line:

if A[i][1] < B[j][1]:
    i += 1
else:
    j += 1

💡 When one pointer reaches the end, the algorithm finishes.

from typing import List

def intervalIntersection(A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
    i, j = 0, 0  # STEP 1
    result = []  # STEP 1
    while i < len(A) and j < len(B):  # STEP 2 loop
        if A[i][1] < B[j][0]:  # STEP 2 compare
            i += 1  # STEP 4 or 7 or 10 or 15 or 18 or 21
        elif B[j][1] < A[i][0]:  # STEP 2 compare
            j += 1  # STEP 5 or 12
        else:  # STEP 3,6,9,14,17,20
            start = max(A[i][0], B[j][0])  # STEP 3,6,9,14,17,20
            end = min(A[i][1], B[j][1])  # STEP 3,6,9,14,17,20
            result.append([start, end])  # STEP 3,6,9,14,17,20
            if A[i][1] < B[j][1]:  # STEP 4,7,10,15,18,21
                i += 1  # STEP 4,7,10,15,18,21
            else:
                j += 1  # STEP 4,7,10,15,18,21
    return result

if __name__ == '__main__':
    A = [[0,2],[5,10],[13,23],[24,25]]
    B = [[1,5],[8,12],[15,24],[25,26]]
    print(intervalIntersection(A, B))

📊

Interval List Intersections - Watch the Algorithm Execute, Step by Step

Watching each pointer movement and comparison reveals how the algorithm efficiently finds all overlapping intervals without unnecessary checks.

setup

j

[0,2]

0

[5,10]

1

[13,23]

2

[24,25]

3

Result: []

compare

j

[0,2]

0

[5,10]

1

[13,23]

2

[24,25]

3

Result: []

record

j

[0,2]

0

[5,10]

1

[13,23]

2

[24,25]

3

Result: [[1,2]]

move_right

j

[0,2]

0

i

[5,10]

1

[13,23]

2

[24,25]

3

Result: [[1,2]]

compare

j

[0,2]

0

i

[5,10]

1

[13,23]

2

[24,25]

3

Result: [[1,2]]

record

j

[0,2]

0

i

[5,10]

1

[13,23]

2

[24,25]

3

Result: [[1,2],[5,5]]

move_right

[0,2]

0

j

[5,10]

1

[13,23]

2

[24,25]

3

Result: [[1,2],[5,5]]

compare

[0,2]

0

j

[5,10]

1

[13,23]

2

[24,25]

3

Result: [[1,2],[5,5]]

record

[0,2]

0

j

[5,10]

1

[13,23]

2

[24,25]

3

Result: [[1,2],[5,5],[8,10]]

move_right

[0,2]

0

j

[5,10]

1

i

[13,23]

2

[24,25]

3

Result: [[1,2],[5,5],[8,10]]

compare

[0,2]

0

j

[5,10]

1

i

[13,23]

2

[24,25]

3

Result: [[1,2],[5,5],[8,10]]

move_right

[0,2]

0

[5,10]

1

j

[13,23]

2

[24,25]

3

Result: [[1,2],[5,5],[8,10]]

compare

[0,2]

0

[5,10]

1

j

[13,23]

2

[24,25]

3

Result: [[1,2],[5,5],[8,10]]

record

[0,2]

0

[5,10]

1

j

[13,23]

2

[24,25]

3

Result: [[1,2],[5,5],[8,10],[15,23]]

move_right

[0,2]

0

[5,10]

1

j

[13,23]

2

i

[24,25]

3

Result: [[1,2],[5,5],[8,10],[15,23]]

compare

[0,2]

0

[5,10]

1

j

[13,23]

2

i

[24,25]

3

Result: [[1,2],[5,5],[8,10],[15,23]]

record

[0,2]

0

[5,10]

1

j

[13,23]

2

i

[24,25]

3

Result: [[1,2],[5,5],[8,10],[15,23],[24,24]]

move_right

[0,2]

0

[5,10]

1

[13,23]

2

j

[24,25]

3

Result: [[1,2],[5,5],[8,10],[15,23],[24,24]]

compare

[0,2]

0

[5,10]

1

[13,23]

2

j

[24,25]

3

Result: [[1,2],[5,5],[8,10],[15,23],[24,24]]

record

[0,2]

0

[5,10]

1

[13,23]

2

j

[24,25]

3

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

move_right

[0,2]

0

[5,10]

1

[13,23]

2

j

[24,25]

3

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

Key Takeaways

✓ Two pointers efficiently find all overlapping intervals by advancing only one pointer at a time.

This insight is hard to see from code alone because the pointer movements depend on interval comparisons and are subtle.

✓ Intervals that touch at a single point (end == start) are considered overlapping and recorded as intersections.

Understanding this prevents confusion about why some intervals with no length appear in the result.

✓ Advancing the pointer with the smaller interval end ensures no potential overlaps are missed while minimizing comparisons.

This decision is key to the algorithm's optimal performance and is clearer when watching pointer movements step-by-step.

Practice

1. Given multiple employees' schedules with intervals representing their busy times, which algorithmic approach guarantees finding all common free time intervals where no employee is busy?

easy

A. Greedy interval scheduling that picks earliest finishing intervals

B. Dynamic programming to find maximum non-overlapping intervals

C. Sweep line / event processing that tracks interval start and end events

D. Brute force checking every time point across all intervals

Solution

1. Step 1: Understand problem requires identifying gaps where no intervals overlap

   Greedy scheduling or DP focus on selecting intervals, not gaps between them.

2. Step 2: Sweep line processes all start/end events in order, tracking active intervals to find free gaps

   This approach efficiently detects when no employee is busy, yielding correct free times.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sweep line tracks active intervals and finds free gaps [OK]

Hint: Sweep line tracks interval endpoints to find free gaps [OK]

Common Mistakes:

• Assuming greedy or DP can find free gaps directly

2. You are given a list of time intervals representing booked meeting rooms. Your task is to combine all overlapping intervals into the minimum number of non-overlapping intervals. Which algorithmic approach guarantees an optimal and efficient solution for this problem?

easy

A. Use a greedy approach that always merges the earliest starting interval with the next one without sorting.

B. Sort intervals by start time and then merge overlapping intervals in a single pass.

C. Use dynamic programming to find the maximum number of non-overlapping intervals and then merge accordingly.

D. Check every pair of intervals with nested loops to merge overlaps until no overlaps remain.

Solution

1. Step 1: Understand the problem requires merging overlapping intervals efficiently.

   Sorting intervals by their start time ensures that overlapping intervals are adjacent, enabling a single pass merge.

2. Step 2: Evaluate each option's approach.

   Use a greedy approach that always merges the earliest starting interval with the next one without sorting. fails because without sorting, intervals may be merged incorrectly or missed. Use dynamic programming to find the maximum number of non-overlapping intervals and then merge accordingly. is unrelated as DP is not needed here. Check every pair of intervals with nested loops to merge overlaps until no overlaps remain. is brute force with O(n²) time, inefficient for large inputs. Sort intervals by start time and then merge overlapping intervals in a single pass. correctly sorts and merges in O(n log n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting + one pass merge is the classic optimal pattern for merging intervals. [OK]

Hint: Sort intervals first, then merge in one pass [OK]

Common Mistakes:

• Trying to merge without sorting
• Using nested loops leading to O(n²) time

3. Consider the following Python function that finds the minimum number of arrows to burst balloons represented as intervals. Given the input points = [[10,16],[2,8],[1,6],[7,12]], what is the value of arrows after processing all intervals?

easy

A. 1

B. 4

C. 3

D. 2

Solution

1. Step 1: Sort intervals by end coordinate

   Sorted points: [[1,6],[2,8],[7,12],[10,16]]

2. Step 2: Iterate and count arrows

   Start with arrow_pos=6, arrows=1. Next interval start=2 ≤ 6 (covered), next start=7 > 6 (new arrow), arrows=2, arrow_pos=12. Next start=10 ≤ 12 (covered).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two arrows suffice to burst all balloons [OK]

Hint: Sort by end, count arrows when start > current arrow position [OK]

Common Mistakes:

• Not sorting intervals before processing
• Using start >= arrow_pos instead of start > arrow_pos
• Off-by-one errors in counting arrows

4. 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

5. 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