Practice
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
Solution
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]].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.Final Answer:
Option A -> Option AQuick Check:
Result matches expected merged intervals [OK]
- Not sorting after insertion leads to wrong order
- Failing to merge intervals that overlap at boundaries
- Appending newInterval multiple times
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
Solution
Step 1: Consider empty intervals input
If intervals is empty, after appending newInterval, intervals has length 1.Step 2: Check initialization of merged
Line 5 accesses intervals[0] without checking if intervals is empty before append, which is safe here but if input was empty, intervals[0] is newInterval, so no crash.Step 3: Identify subtle bug
Actually, no crash here, but if input intervals was empty, sorting and merging still works. The subtle bug is that if intervals was empty and newInterval is appended, the code works, but if the initial intervals list is empty and the code did not append newInterval first, line 5 would crash. So the bug is that the code assumes intervals is non-empty before append, which is not always true.Final Answer:
Option A -> Option AQuick Check:
Accessing intervals[0] without empty check is risky [OK]
- Not handling empty input intervals list
- Assuming intervals always non-empty before append
- Incorrect merging when intervals just touch
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
from typing import List
def can_attend_meetings(intervals: List[List[int]]) -> bool:
intervals.sort(key=lambda x: x[0])
end = float('-inf')
for interval in intervals:
if interval[0] <= end:
return False
end = interval[1]
return True
Solution
Step 1: Understand the overlap condition
Meetings that just touch (e.g., end=5 and start=5) should not be considered overlapping.Step 2: Identify the bug
The condition uses <= which incorrectly treats touching intervals as overlapping. It should use < instead.Final Answer:
Option A -> Option AQuick Check:
Changing <= to < fixes false positives on touching intervals [OK]
- Using <= causes false overlap detection on touching intervals
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 CQuick Check:
Segment trees handle range queries with repeated intervals efficiently [OK]
- Assuming line sweep handles infinite repeats
- Trying to expand events explicitly
- Merging intervals loses count accuracy
