Practice
Solution
Step 1: Sort events and process starts
Events: (1,+1), (2,+1), (2,0), (5,0), (5+1,-1), (4+1,-1), (7,+1), (8,0), (9+1,-1). Sorted order processes starts before points, points before ends.Step 2: Track active intervals and assign counts at points
At point 2: active=2 (intervals [1,4],[2,5]), at point 5: active=1 (only [2,5] ends at 6), at point 8: active=0 (interval [7,9] ended at 10, but 8 < 10 so active=1 actually, re-check)Correction Step 2:
At point 8: interval [7,9] is active, so active=1. So final counts: [2,1,1]Final Answer:
Option B -> Option BQuick Check:
Counting active intervals at each point matches expected output [OK]
- Forgetting end+1 shifts interval end
- Misordering events causing wrong active count
- Off-by-one in active count at points
Solution
Step 1: Understand the problem requirement
The problem asks if a single person can attend all meetings without overlap, so we must check if any intervals overlap.Step 2: Identify the correct approach
Sorting intervals by start time and checking if any interval starts before the previous one ends guarantees detection of overlaps efficiently.Final Answer:
Option B -> Option BQuick Check:
Sorting by start time and checking overlaps is the standard approach [OK]
- Confusing sorting by end time with start time for overlap detection
def intervalIntersection(A, B):
i, j = 0, 0
result = []
while i < len(A) and j < len(B):
if A[i][1] <= B[j][0]:
i += 1
elif B[j][1] < A[i][0]:
j += 1
else:
start = max(A[i][0], B[j][0])
end = min(A[i][1], B[j][1])
result.append([start, end])
if A[i][1] < B[j][1]:
i += 1
else:
j += 1
return result
What is the bug in this code?Solution
Step 1: Analyze overlap condition
Using '<=' excludes intervals that touch at a point (e.g., end == start), missing valid intersections.Step 2: Correct condition
Changing to '<' ensures intervals that share a boundary point are considered intersecting.Final Answer:
Option A -> Option AQuick Check:
Inclusive endpoints require '<' not '<=' to detect touching intervals [OK]
- Using <= instead of <
- Reversing pointer increments
- Ignoring empty inputs
def min_interval_binary_search(intervals, queries):
intervals.sort(key=lambda x: x[1] - x[0] + 1)
lengths = [end - start for start, end in intervals]
starts = [start for start, end in intervals]
ends = [end for start, end in intervals]
def covers(query, length):
idx = bisect.bisect_right(lengths, length)
for i in range(idx):
if starts[i] <= query <= ends[i]:
return True
return False
res = []
max_len = lengths[-1] if lengths else 0
for q in queries:
left, right = 1, max_len
ans = -1
while left <= right:
mid = (left + right) // 2
if covers(q, mid):
ans = mid
right = mid - 1
else:
left = mid + 1
res.append(ans)
return resSolution
Step 1: Check interval length calculation
Line 3 calculates lengths as end - start, missing the +1 needed for inclusive intervals.Step 2: Impact of bug
Incorrect lengths cause wrong sorting order and coverage checks, leading to wrong minimal interval lengths.Final Answer:
Option D -> Option DQuick Check:
Correct interval length must be end - start + 1 [OK]
- Off-by-one in length calculation
- Not sorting intervals
- Incorrect binary search boundaries
Solution
Step 1: Identify sorting cost
Sorting n intervals by start and end takes O(n log n) time.Step 2: Identify scanning cost
Single pass scanning to count uncovered intervals is O(n).Final Answer:
Option A -> Option AQuick Check:
Sorting dominates, scanning is linear [OK]
- Confuse scanning as nested loops O(n²)
- Ignore sorting cost and say O(n)
