[Solved] The following code attempts to compute the ... Identify the line containing the subtle bug that can cause incorrect platform count when a train arrives exactly at the departure time of another train. | Greedy Algorithms

Greedy Algorithms - Minimum Platforms (Train Stations)

The following code attempts to compute the minimum number of platforms needed. Identify the line containing the subtle bug that can cause incorrect platform count when a train arrives exactly at the departure time of another train.

ALine with 'while heap and heap[0] < arrival:'

BLine with 'trains = sorted(zip(arrivals, departures), key=lambda x: x[0])'

CLine with 'heapq.heappush(heap, departure)'

DLine with 'max_platforms = max(max_platforms, len(heap))'

Step-by-Step Solution

Solution:

Step 1: Understand the bug
The condition 'heap[0] < arrival' pops platforms only if departure is strictly less than arrival, missing the case when departure == arrival.
Step 2: Correct condition
Changing condition to 'heap[0] <= arrival' correctly frees platforms when a train arrives exactly at departure time, avoiding overcounting.
Final Answer:
Option A -> Option A
Quick Check:
Condition must include equality to avoid platform overcount [OK]

Quick Trick: Use <= to free platform when arrival equals departure [OK]

Common Mistakes:

MISTAKES

Using < instead of <= in heap pop condition
Not sorting trains by arrival time
Forgetting to update max_platforms

Trap Explanation:

PITFALL

Using < looks correct but causes subtle overcount when trains arrive exactly at departure time.

Interviewer Note:

CONTEXT

Tests attention to boundary conditions and off-by-one errors in greedy algorithms.

Master "Minimum Platforms (Train Stations)" in Greedy Algorithms

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

More Greedy Algorithms Quizzes

Identify the line containing the subtle bug that can cause incorrect platform count when a train arrives exactly at the departure time of another train.

Step 1: Understand the bug

Step 2: Correct condition

Final Answer:

Quick Check:

Want More Practice?