After processing all events, we return max_platforms, which is 3.
💡 This value represents the minimum number of platforms required to avoid conflicts.
Line:return max_platforms
💡 The maximum platforms needed at any time is the answer to the problem.
def min_platforms_sweep_line(arrivals, departures):
events = []
# STEP 1: Create arrival events
for time in arrivals:
events.append((time, 1)) # arrival
# STEP 2: Create departure events
for time in departures:
events.append((time, -1)) # departure
# STEP 3: Sort events by time and type
events.sort(key=lambda x: (x[0], x[1]))
# STEP 4: Initialize counters
platforms_needed = max_platforms = 0
# STEP 5-16: Process each event
for i, (_, event_type) in enumerate(events):
platforms_needed += event_type # STEP i+5
max_platforms = max(max_platforms, platforms_needed)
# STEP 17: Return result
return max_platforms
if __name__ == '__main__':
arrivals = [900, 940, 950, 1100, 1500, 1800]
departures = [910, 1200, 1120, 1130, 1900, 2000]
print(min_platforms_sweep_line(arrivals, departures)) # Output: 3
📊
Minimum Number of Platforms Required - Watch the Algorithm Execute, Step by Step
Watching the algorithm process each event one by one reveals how overlapping intervals cause platform requirements to increase and decrease, making the concept of sweep line intuitive.
✓ Sorting events by time and prioritizing departures before arrivals at the same time is crucial.
This prevents overcounting platforms when trains arrive and depart simultaneously, which is not obvious from code alone.
✓ The sweep line approach converts interval overlap into a simple running count problem.
Visualizing events as points on a timeline helps understand how overlaps translate to platform needs.
✓ Tracking both current platforms needed and maximum platforms needed separately is essential.
The maximum platforms needed is the final answer, but the current count fluctuates as events are processed.
Practice
(1/5)
1. 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
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 A
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
2. Consider the following Python function implementing the binary search approach for the minimum interval problem. Given intervals = [[1,4],[2,4],[3,6]] and queries = [2,5], what is the output of the function call min_interval_binary_search(intervals, queries)?
easy
A. [3, 4]
B. [3, 4]
C. [3, 4]
D. [3, 4]
Solution
Step 1: Sort intervals by length
Intervals sorted by length: [2,4] length=3, [1,4] length=4, [3,6] length=4.
Step 2: Binary search for each query
Query=2: smallest interval covering 2 is length=3 ([2,4]). Query=5: smallest interval covering 5 is length=4 ([3,6]).
Final Answer:
Option B -> Option B
Quick Check:
Output matches expected minimal interval lengths for queries [OK]
Hint: Trace binary search narrowing on interval lengths [OK]
Common Mistakes:
Off-by-one in interval length calculation
Incorrect binary search boundaries
Confusing start and end indices
3. Examine the following buggy code for interval intersections:
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?
medium
A. The condition 'if A[i][1] <= B[j][0]' should use '<' instead of '<=' to correctly detect touching intervals.
B. The pointer increments inside the else block are reversed; they should increment the pointer with the larger endpoint.
C. The overlap condition should check 'start < end' instead of 'start <= end' to avoid zero-length intervals.
D. The code does not handle empty input lists, which can cause runtime errors.
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 A
Quick Check:
Inclusive endpoints require '<' not '<=' to detect touching intervals [OK]
Hint: Check boundary conditions carefully for inclusive intervals [OK]
Common Mistakes:
Using <= instead of <
Reversing pointer increments
Ignoring empty inputs
4. The following code attempts to merge intervals in-place after sorting. Identify the line that contains a subtle bug causing incorrect results on some inputs.
medium
A. Line 3: intervals.sort(key=lambda x: x[0])
B. Line 9: intervals[index][1] = max(intervals[index][1], intervals[i][1])
C. Line 12: return intervals # missing slicing after in-place merge
D. Line 8: if intervals[i][0] <= intervals[index][1]:
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 C
Quick Check:
Return intervals[:index+1] to exclude leftover intervals. [OK]
Hint: Return sliced intervals after in-place merge [OK]
Common Mistakes:
Forgetting to slice after in-place merge
Modifying list while iterating without adjusting index
5. 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
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.