Minimum Interval to Include Each Query

▶

Steps

setup

Sort intervals by length

Intervals are sorted by their length (end - start + 1). This prepares for binary searching over interval lengths.

💡 Sorting by length allows us to consider intervals from smallest to largest, which is key to finding the minimal covering interval efficiently.

Line:

intervals.sort(key=lambda x: x[1] - x[0] + 1)

💡 Sorted intervals enable binary search on lengths to find minimal covering intervals.

setup

Compute lengths, starts, and ends arrays

Lengths, starts, and ends arrays are created from the sorted intervals for quick access during coverage checks.

💡 Separating these arrays simplifies binary search and coverage checks by focusing on interval properties independently.

Line:

lengths = [end - start + 1 for start, end in intervals]
starts = [start for start, end in intervals]
ends = [end for start, end in intervals]

💡 Preprocessing interval properties enables efficient binary search and coverage verification.

traverse

Start processing query 2

Begin binary search for query=2 to find the smallest interval length covering it. Initialize left=1, right=4 (max length).

💡 Binary search narrows down the minimal interval length that covers the query efficiently.

Line:

left, right = 1, max_len
ans = -1

💡 Setting search boundaries based on max interval length focuses the search.

compare

Calculate mid for query=2

Calculate mid = (left + right) // 2 = 2 to check if any interval of length <= 2 covers query=2.

💡 Midpoint divides the search space to test coverage at a specific length.

Line:

mid = (left + right) // 2

💡 Midpoint guides the binary search to narrow down the minimal covering length.

compare

Check coverage for query=2 with length <= 2

Check intervals with length <= 2. Only interval with length 1 is considered but it does not cover query=2.

💡 Coverage check confirms if the current length candidate can cover the query.

Line:

idx = bisect.bisect_right(lengths, mid)
for i in range(idx):
  if starts[i] <= query <= ends[i]:
    return True

💡 Coverage check filters intervals by length and verifies query inclusion.

shrink

Update binary search bounds after no coverage (query=2)

Since no coverage found for length=2, move left to mid+1=3 to search larger intervals.

💡 Adjusting search bounds focuses on larger intervals that might cover the query.

Line:

left = mid + 1

💡 Binary search narrows the search space based on coverage results.

compare

Calculate mid again for query=2

Calculate mid = (left + right) // 2 = 3 to check coverage for length=3.

💡 Mid recalculation continues binary search in the updated range.

Line:

mid = (left + right) // 2

💡 Midpoint guides the next coverage check.

compare

Check coverage for query=2 with length <= 3

Intervals with length <= 3 are considered. Interval [2,4] (length 3) covers query=2, coverage is True.

💡 Finding coverage here means we can try to find smaller intervals or confirm this as minimal.

Line:

idx = bisect.bisect_right(lengths, mid)
for i in range(idx):
  if starts[i] <= query <= ends[i]:
    return True

💡 Coverage check confirms minimal interval length candidate.

shrink

Update binary search bounds after coverage found (query=2)

Since coverage found at length=3, update answer=3 and move right to 2 to try smaller lengths.

💡 Trying smaller lengths ensures minimal interval is found.

Line:

ans = mid
right = mid - 1

💡 Binary search narrows down to minimal covering length.

record

Binary search ends for query=2, record answer

Binary search ends as left > right. The minimal interval length covering query=2 is 3, recorded in results.

💡 Recording the answer finalizes the search for this query.

Line:

res.append(ans)

💡 Binary search successfully found minimal covering interval length.

from typing import List
import bisect

def min_interval_binary_search(intervals: List[List[int]], queries: List[int]) -> List[int]:
    # STEP 1: Sort intervals by length
    intervals.sort(key=lambda x: x[1] - x[0] + 1)  # STEP 1
    lengths = [end - start + 1 for start, end in intervals]  # STEP 2
    starts = [start for start, end in intervals]  # STEP 2
    ends = [end for start, end in intervals]  # STEP 2

    def covers(query, length):  # STEP 5
        idx = bisect.bisect_right(lengths, length)  # STEP 5
        for i in range(idx):  # STEP 5
            if starts[i] <= query <= ends[i]:  # STEP 5
                return True  # STEP 5
        return False  # STEP 5

    res = []  # STEP 3
    max_len = lengths[-1] if lengths else 0  # STEP 3
    for q in queries:  # STEP 3
        left, right = 1, max_len  # STEP 3
        ans = -1  # STEP 3
        while left <= right:  # STEP 4
            mid = (left + right) // 2  # STEP 4
            if covers(q, mid):  # STEP 5
                ans = mid  # STEP 6
                right = mid - 1  # STEP 6
            else:  # STEP 7
                left = mid + 1  # STEP 7
        res.append(ans)  # STEP 10
    return res  # STEP 10

📊

Minimum Interval to Include Each Query - Watch the Algorithm Execute, Step by Step

Watching each pointer move and comparison helps you understand how sorting by length and binary searching over lengths leads to an optimal solution.

move_right

[4,4]

0

[1,4]

1

[2,4]

2

[3,6]

3

Result: []

move_right

lengths: 1,4,3,4

0

starts: 4,1,2,3

1

ends: 4,4,4,6

2

Result: []

compare

left

1

0

4

1

3

2

right

4

3

Result: []

compare

query

1

0

mid

4

1

3

2

right

4

3

Result: []

compare

length_check

lengths: 1,4,3,4

0

starts: 4,1,2,3

1

ends: 4,4,4,6

2

Result: []

move_left

query

1

0

4

1

left

3

2

right

4

3

Result: []

compare

query

1

0

4

1

mid

3

2

right

4

3

Result: []

compare

query

lengths: 1,4,3,4

0

starts: 4,1,2,3

1

length_check

ends: 4,4,4,6

2

Result: []

move_right

query

1

0

right

4

1

left

3

2

4

3

Result: []

record

query

3

0

Result: [3]

Key Takeaways

✓ Sorting intervals by length allows binary searching over interval sizes to efficiently find the minimal covering interval for each query.

This insight is hard to see from code alone because it requires understanding why sorting by length enables binary search on interval sizes.

✓ Binary search narrows the search space by checking coverage at mid-length intervals, adjusting bounds based on coverage results.

Watching pointer movements and coverage checks visually clarifies how the search space shrinks step-by-step.

✓ Coverage checks filter intervals by length and verify if the query lies within any interval, determining if the current length candidate is valid.

Seeing coverage checks in action helps understand why some lengths are rejected or accepted during binary search.

Practice

1. Consider the following Python code implementing the optimal approach for maintaining disjoint intervals. After executing addNum(1), addNum(3), and addNum(2) in order, what is the final state of self.intervals?

easy

A. [[1, 1], [3, 3]]

B. [[1, 1], [2, 3]]

C. [[1, 2], [3, 3]]

D. [[1, 3]]

Solution

1. Step 1: Trace addNum(1)

   Intervals empty, append [1,1]. Intervals = [[1,1]]

2. Step 2: Trace addNum(3) and addNum(2)

   addNum(3): bisect_left finds i=1, no merges, insert [3,3]. Intervals = [[1,1],[3,3]]. addNum(2): bisect_left finds i=1, left_merge true (1's end +1 == 2), right_merge true (3's start -1 == 2), merge intervals[0] and intervals[1] into [1,3], pop intervals[1]. Intervals = [[1,3]]

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Intervals correctly merged into one [OK]

Hint: Merging occurs when val bridges two intervals [OK]

Common Mistakes:

• Forgetting to merge both sides
• Inserting duplicates
• Off-by-one errors in merging

2. Given the following code for inserting an interval, what is the final returned list after calling insert([[1,3],[6,9]], [2,5])?

from typing import List

def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    intervals.append(newInterval)
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for i in range(1, len(intervals)):
        if intervals[i][0] <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], intervals[i][1])
        else:
            merged.append(intervals[i])
    return merged

easy

A. [[1,5],[6,9]]

B. [[1,3],[2,5],[6,9]]

C. [[1,3],[6,9],[2,5]]

D. [[1,9]]

Solution

1. Step 1: Append and sort intervals

   After appending [2,5], intervals become [[1,3],[6,9],[2,5]]. Sorting by start time yields [[1,3],[2,5],[6,9]].

2. Step 2: Merge overlapping intervals

   Start with merged = [[1,3]]. The next interval [2,5] overlaps since 2 <= 3, so merge to [1,5]. Next interval [6,9] does not overlap, so append it.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Result matches expected merged intervals [OK]

Hint: Sort after insertion, then merge overlapping intervals [OK]

Common Mistakes:

• Not sorting after insertion leads to wrong order
• Failing to merge intervals that overlap at boundaries
• Appending newInterval multiple times

3. You are given a set of intervals representing horizontal balloons on a number line. Each balloon can be burst by shooting an arrow vertically through any point covered by the balloon's interval. What is the most efficient approach to find the minimum number of arrows needed to burst all balloons?

easy

A. Sort intervals by their end coordinate and greedily shoot arrows at the earliest possible end to cover maximum balloons.

B. Sort intervals by their start coordinate and greedily shoot arrows at the start of each balloon.

C. Use dynamic programming to find the maximum number of overlapping intervals and subtract from total balloons.

D. Use a brute force nested loop to check all pairs of intervals for overlaps and count arrows accordingly.

Solution

1. Step 1: Understand the problem constraints

   The problem requires minimizing arrows to burst all balloons, which translates to covering intervals with minimum points.

2. Step 2: Identify the optimal greedy strategy

   Sorting by end coordinate allows shooting an arrow at the earliest finishing balloon's end, covering all overlapping balloons starting before that point.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting by end coordinate ensures minimal arrows by maximizing coverage [OK]

Hint: Sort intervals by end to greedily cover overlaps [OK]

Common Mistakes:

• Sorting by start coordinate and shooting at start misses optimal overlaps
• Using DP unnecessarily complicates the problem
• Brute force is too slow for large inputs

4. What is the time complexity of the optimal approach that inserts a new interval into a list of n intervals and merges overlapping intervals, where the approach is to append the new interval, sort all intervals by start time, then merge in one pass?

medium

A. O(n)

B. O(n^2)

C. O(n log n)

D. O(log n)

Solution

1. Step 1: Identify sorting cost

   Appending is O(1), but sorting n+1 intervals takes O(n log n) time.

2. Step 2: Identify merging cost

   Merging intervals in one pass is O(n) since each interval is processed once.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting dominates overall time complexity [OK]

Hint: Sorting dominates time complexity -> O(n log n) [OK]

Common Mistakes:

• Assuming linear time because merging is O(n)
• Confusing sorting cost with merging cost
• Thinking recursion stack adds extra complexity

5. Suppose the problem is extended so that numbers can be added multiple times (duplicates allowed), and the intervals must reflect the count of each number (e.g., intervals store counts of coverage). Which modification to the optimal balanced tree approach is necessary to handle this correctly?

hard

A. Augment intervals with counts and update counts on insertion; merge intervals only if counts allow.

B. Keep the current approach but ignore duplicates since intervals are disjoint sets.

C. Use a brute force approach storing all numbers and recomputing intervals with counts on each query.

D. Replace balanced tree with a hash map keyed by number to track counts and intervals separately.

Solution

1. Step 1: Understand the impact of duplicates

   Intervals must now track counts, so simple presence is insufficient.

2. Step 2: Modify data structure

   Intervals should store counts per interval or per number; merging must consider counts to avoid losing duplicates.

3. Step 3: Evaluate options

   Ignoring duplicates (B) breaks correctness. Brute force (C) is inefficient. Hash map (D) loses interval ordering benefits. Augmenting intervals with counts (A) preserves efficiency and correctness.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Counting duplicates requires augmenting intervals [OK]

Hint: Track counts in intervals to handle duplicates correctly [OK]

Common Mistakes:

• Ignoring duplicates
• Using brute force for counts
• Losing interval order with hash maps