Practice
Solution
Step 1: Sort intervals by start time.
Input is already sorted: [[1,4],[2,5],[7,9]].Step 2: Merge intervals in one pass.
Compare [2,5] with [1,4]: overlap since 2 <= 4, merge to [1,5]. Then compare [7,9] with [1,5]: no overlap, move index forward and assign [7,9]. Final intervals: [[1,5],[7,9]].Final Answer:
Option A -> Option AQuick Check:
Overlapping intervals merged correctly, non-overlapping preserved. [OK]
- Returning original intervals without merging
- Off-by-one slicing errors
Solution
Step 1: Understand the problem requires tracking concurrent trains
The key is to find the maximum number of trains present at the station simultaneously.Step 2: Recognize that sorting events and sweeping through them tracks concurrency efficiently
By creating arrival and departure events and sorting them, we can increment or decrement the count of trains present, capturing the peak count.Final Answer:
Option B -> Option BQuick Check:
Sweep line tracks concurrency optimally [OK]
- Assuming greedy assignment without sorting works
- Trying DP which is unnecessary overhead
- Using nested loops which is inefficient
addNum operation in the optimal balanced tree approach for maintaining disjoint intervals, assuming there are n intervals stored?Solution
Step 1: Identify main operations in addNum
addNum uses binary search (bisect_left) to find insertion index in O(log n).Step 2: Analyze merging cost
Merging involves at most constant number of interval merges (left, right, or both), so O(1) extra work.Final Answer:
Option B -> Option BQuick Check:
Binary search dominates, merges are constant time [OK]
- Assuming linear scan for merging
- Confusing sorting cost per insertion
- Ignoring constant merge steps
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
Solution
Step 1: Understand the in-place merge modifies intervals up to index.
After merging, only intervals[:index+1] are valid merged intervals.Step 2: Identify the bug in the return statement.
Returning the entire intervals list without slicing includes extra unmerged intervals, causing incorrect output.Final Answer:
Option C -> Option CQuick Check:
Return intervals[:index+1] to exclude leftover intervals. [OK]
- Forgetting to slice after in-place merge
- Modifying list while iterating without adjusting index
