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.
Step 1/10
·Active fill★Answer cell
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/5)
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?
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]]
Final Answer:
Option D -> Option D
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. The following code attempts to find the maximum number of non-overlapping intervals. Which line contains a subtle bug that can cause incorrect results on some inputs?
def max_non_overlapping_intervals(intervals):
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
medium
A. Line 9: Updating last_end to intervals[i][1] when no overlap
B. Line 2: Sorting intervals by start time instead of end time
C. Line 7: Updating last_end to min(last_end, intervals[i][1]) inside overlap condition
D. Line 5: Using '<=' instead of '<' in the overlap condition
Solution
Step 1: Understand overlap condition
Intervals that start exactly at last_end do not overlap and should be allowed.
Step 2: Identify incorrect operator
Using '<=' causes intervals starting exactly at last_end to be considered overlapping, reducing count incorrectly.
Final Answer:
Option D -> Option D
Quick Check:
Change '<=' to '<' fixes the bug [OK]
Hint: Overlap check must use strict less than, not less or equal [OK]
Common Mistakes:
Confusing inclusive vs exclusive overlap conditions
Sorting by start time is allowed but less optimal
Incorrect last_end updates
3. Suppose the problem changes: intervals can be reused infinitely many times, and you want to count how many intervals contain each point considering unlimited reuse (e.g., intervals repeat periodically). Which modification to the line sweep approach correctly handles this scenario?
hard
A. No change needed; line sweep already counts intervals correctly regardless of reuse.
B. Preprocess intervals to merge overlapping intervals into one, then run line sweep once.
C. Use a segment tree or binary indexed tree to handle repeated intervals efficiently instead of line sweep.
D. Modify events to include multiple copies of intervals explicitly and run line sweep on expanded events.
Solution
Step 1: Understand reuse impact
Infinite reuse means intervals repeat periodically, so naive line sweep with explicit events cannot handle infinite copies.
Step 2: Recognize data structure need
Segment trees or binary indexed trees can efficiently query counts over ranges and handle repeated intervals without enumerating all copies.
Step 3: Why other options fail
No change (A) ignores infinite reuse; merging (B) loses count detail; explicit expansion (D) is infeasible for infinite repeats.
Final Answer:
Option C -> Option C
Quick Check:
Segment trees handle range queries with repeated intervals efficiently [OK]
Hint: Infinite reuse requires data structures, not event enumeration [OK]
Common Mistakes:
Assuming line sweep handles infinite repeats
Trying to expand events explicitly
Merging intervals loses count accuracy
4. Suppose trains can arrive and depart multiple times (reusing platforms) and the schedule may include negative time values (e.g., early morning times). Which modification to the sweep line algorithm ensures correct minimum platform calculation?
hard
A. Use the same sweep line approach but ensure sorting handles negative times correctly and process events with departure before arrival on tie.
B. Use dynamic programming to handle multiple arrivals and departures per train.
C. Switch to nested loops checking overlaps since negative times break sorting assumptions.
D. Ignore negative times and treat them as zero to simplify sorting.
Solution
Step 1: Recognize that negative times do not affect event sorting if handled correctly
Sorting supports negative values naturally; no need to ignore or clamp them.
Step 2: Maintain departure-before-arrival ordering on tie to avoid overcounting
This ordering is critical regardless of time values or multiple arrivals/departures.
Step 3: Continue using sweep line approach for efficiency and correctness
Nested loops or DP are inefficient or unnecessary for this variant.
Final Answer:
Option A -> Option A
Quick Check:
Sweep line with correct sorting handles negative and multiple events [OK]
Hint: Sorting handles negative times; keep departure before arrival on tie [OK]
Common Mistakes:
Ignoring negative times or clamping them
Switching to inefficient nested loops unnecessarily
Misordering events causing overcounting
5. Suppose intervals can have negative values and zero length (start == end). Which modification to the optimal solution is necessary to correctly remove covered intervals?
hard
A. Change sorting to (start ascending, end ascending) to handle zero-length intervals correctly.
B. Use strict inequality 'if end > max_end' to avoid counting zero-length intervals as uncovered.
C. Switch to brute force nested loops to handle negative and zero-length intervals safely.
D. Keep sorting by (start ascending, end descending) and use 'if end >= max_end' to include zero-length coverage cases.
Solution
Step 1: Consider zero-length intervals
Zero-length intervals (start == end) require coverage detection to include intervals with equal ends.
Step 2: Adjust inequality and sorting
Sorting by start ascending and end descending remains correct; change condition to 'if end >= max_end' to count intervals not strictly greater but equal ends.
Final Answer:
Option D -> Option D
Quick Check:
Using >= includes zero-length coverage correctly without changing sorting [OK]
Hint: Use >= in condition to handle zero-length intervals [OK]
Common Mistakes:
Changing sorting breaks coverage detection
Using strict > misses zero-length coverage
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.