Minimum Platforms (Train Stations)

▶

Steps

setup

Sort trains by arrival time

We pair each train's arrival and departure times and sort them by arrival to process trains in chronological order.

💡 Sorting ensures we consider trains in the order they arrive, which is essential for correct platform allocation.

Line:

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

💡 Sorting by arrival time sets the foundation for a greedy approach to assign platforms efficiently.

setup

Initialize empty min-heap for departures

We create an empty min-heap to keep track of the earliest departure times of trains currently occupying platforms.

💡 The min-heap helps us quickly find which platform frees up earliest to reuse it if possible.

Line:

heap = []

💡 An empty heap means no platforms are occupied initially.

traverse

Process first train arrival

We look at the first train arriving at 900 and check if any platform is free by comparing with heap top (empty now).

💡 Since no platforms are occupied, we allocate a new platform for this train.

Line:

for arrival, departure in trains:
    while heap and heap[0] <= arrival:
        heapq.heappop(heap)
    heapq.heappush(heap, departure)

💡 The first train always requires a new platform.

traverse

Process second train arrival

The second train arrives at 940. We check if the earliest platform frees up by 940 by comparing with heap top (910).

💡 Since 910 <= 940, the platform from the first train is now free and can be reused.

Line:

while heap and heap[0] <= arrival:
    heapq.heappop(heap)

💡 Platforms can be reused if the previous train departs before the next arrives.

insert

Allocate platform for second train

We push the second train's departure time (1200) into the heap, representing platform allocation.

💡 Adding departure time to heap tracks when this platform will be freed next.

Line:

heapq.heappush(heap, departure)

💡 Heap size remains 1, indicating one platform is currently occupied.

traverse

Process third train arrival

The third train arrives at 950. We check if any platform frees up by 950 by comparing with heap top (1200).

💡 Since 1200 > 950, no platform is free; we must allocate a new platform.

Line:

while heap and heap[0] <= arrival:
    heapq.heappop(heap)

💡 Overlapping trains increase platform requirements.

insert

Allocate platform for third train

We push the third train's departure time (1120) into the heap, increasing platform count.

💡 Heap now has two departure times, meaning two platforms are occupied simultaneously.

Line:

heapq.heappush(heap, departure)

💡 Platform count increases as trains overlap in time.

traverse

Process fourth train arrival

The fourth train arrives at 1100. We check if any platform frees up by 1100 by comparing with heap top (1120).

💡 Since 1120 > 1100, no platform is free; we must allocate another platform.

Line:

while heap and heap[0] <= arrival:
    heapq.heappop(heap)

💡 More overlapping trains increase platform requirements.

insert

Allocate platform for fourth train

We push the fourth train's departure time (1130) into the heap, increasing platform count to 3.

💡 Heap size 3 means three platforms are occupied simultaneously.

Line:

heapq.heappush(heap, departure)

💡 Maximum platforms needed so far is updated to 3.

traverse

Process fifth train arrival

The fifth train arrives at 1500. We check if any platform frees up by 1500 by popping all departures <= 1500.

💡 We pop 1120, 1130, and 1200 from heap as all these trains have departed before 1500.

Line:

while heap and heap[0] <= arrival:
    heapq.heappop(heap)

💡 Multiple platforms free up before this train arrives, allowing reuse.

insert

Allocate platform for fifth train

We push the fifth train's departure time (1900) into the heap, occupying one platform.

💡 Heap size is now 1, showing one platform occupied after freeing others.

Line:

heapq.heappush(heap, departure)

💡 Platform count does not increase beyond previous max of 3.

traverse

Process sixth train arrival

The sixth train arrives at 1800. We check if any platform frees up by 1800 by popping departures <= 1800.

💡 Since 1900 > 1800, no platform is freed; the current platform remains occupied.

Line:

while heap and heap[0] <= arrival:
    heapq.heappop(heap)

💡 Platform remains occupied as train has not departed yet.

insert

Allocate platform for sixth train

We push the sixth train's departure time (2000) into the heap, increasing platform count to 2 currently occupied.

💡 Heap size increases but max platforms remains 3 as previous max was higher.

Line:

heapq.heappush(heap, departure)

💡 Current platform usage is tracked accurately with heap size.

reconstruct

Return maximum platforms needed

After processing all trains, we return the maximum number of platforms needed, which is 3.

💡 This final value represents the minimum platforms required to avoid train waiting.

Line:

return max_platforms

💡 The algorithm efficiently computes the minimum platforms by tracking overlapping trains.

import heapq

def min_platforms_min_heap(arrivals, departures):
    trains = sorted(zip(arrivals, departures), key=lambda x: x[0])  # STEP 1
    heap = []  # STEP 2
    max_platforms = 0
    for arrival, departure in trains:  # STEP 3
        while heap and heap[0] <= arrival:  # STEP 4
            heapq.heappop(heap)  # STEP 4
        heapq.heappush(heap, departure)  # STEP 5
        max_platforms = max(max_platforms, len(heap))  # STEP 6
    return max_platforms  # STEP 14

if __name__ == '__main__':
    arrivals = [900, 940, 950, 1100, 1500, 1800]
    departures = [910, 1200, 1120, 1130, 1900, 2000]
    print(min_platforms_min_heap(arrivals, departures))

📊

Minimum Platforms (Train Stations) - Watch the Algorithm Execute, Step by Step

Watching each step shows how the algorithm efficiently manages platforms by reusing freed ones, which is hard to grasp from code alone.

setup

i

(900,910)

0

(940,1200)

1

(950,1120)

2

(1100,1130)

3

(1500,1900)

4

(1800,2000)

5

Result: 0

setup

i

(900,910)

0

(940,1200)

1

(950,1120)

2

(1100,1130)

3

(1500,1900)

4

(1800,2000)

5

Result: 0

insert

i

(900,910)

0

(940,1200)

1

(950,1120)

2

(1100,1130)

3

(1500,1900)

4

(1800,2000)

5

Result: 1

delete

(900,910)

0

i

(940,1200)

1

(950,1120)

2

(1100,1130)

3

(1500,1900)

4

(1800,2000)

5

Result: 1

insert

(900,910)

0

i

(940,1200)

1

(950,1120)

2

(1100,1130)

3

(1500,1900)

4

(1800,2000)

5

Result: 1

compare

(900,910)

0

(940,1200)

1

i

(950,1120)

2

(1100,1130)

3

(1500,1900)

4

(1800,2000)

5

Result: 1

insert

(900,910)

0

(940,1200)

1

i

(950,1120)

2

(1100,1130)

3

(1500,1900)

4

(1800,2000)

5

Result: 2

compare

(900,910)

0

(940,1200)

1

(950,1120)

2

i

(1100,1130)

3

(1500,1900)

4

(1800,2000)

5

Result: 2

insert

(900,910)

0

(940,1200)

1

(950,1120)

2

i

(1100,1130)

3

(1500,1900)

4

(1800,2000)

5

Result: 3

delete

(900,910)

0

(940,1200)

1

(950,1120)

2

(1100,1130)

3

i

(1500,1900)

4

(1800,2000)

5

Result: 3

insert

(900,910)

0

(940,1200)

1

(950,1120)

2

(1100,1130)

3

i

(1500,1900)

4

(1800,2000)

5

Result: 3

compare

(900,910)

0

(940,1200)

1

(950,1120)

2

(1100,1130)

3

(1500,1900)

4

i

(1800,2000)

5

Result: 3

insert

(900,910)

0

(940,1200)

1

(950,1120)

2

(1100,1130)

3

(1500,1900)

4

i

(1800,2000)

5

Result: 3

record

(900,910)

0

(940,1200)

1

(950,1120)

2

(1100,1130)

3

(1500,1900)

4

(1800,2000)

5

Result: 3

Key Takeaways

✓ Sorting trains by arrival time is crucial to process them in chronological order.

Without sorting, the algorithm cannot correctly allocate platforms as it relies on sequential arrival processing.

✓ Using a min-heap to track earliest departure times allows efficient reuse of platforms.

The heap quickly identifies which platform frees up next, avoiding unnecessary platform allocation.

✓ The maximum heap size during iteration equals the minimum number of platforms needed.

This insight connects the data structure state directly to the problem's answer, which is not obvious from code alone.

Practice

1. Consider the following code snippet for the Jump Game problem. What is the value of maxReach after the third iteration (i = 2) when the input is [2, 3, 1, 1, 4]?

def canJump(nums):
    maxReach = 0
    for i, jump in enumerate(nums):
        if i > maxReach:
            return False
        maxReach = max(maxReach, i + jump)
        if maxReach >= len(nums) - 1:
            return True
    return False

easy

A. 3

B. 4

C. 5

D. 2

Solution

1. Step 1: Trace maxReach updates for each iteration

   i=0: maxReach = max(0, 0+2) = 2 i=1: maxReach = max(2, 1+3) = 4 i=2: maxReach = max(4, 2+1) = 4

2. Step 2: Identify maxReach after i=2

   After third iteration (i=2), maxReach remains 4.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   maxReach does not decrease; it stays at 4 after i=2 [OK]

Hint: maxReach never decreases, track max(i+jump) [OK]

Common Mistakes:

• Off-by-one in iteration count
• Confusing maxReach update with i only

2. You have different types of boxes, each with a number of boxes and units per box. You want to load a truck with a limited capacity to maximize total units. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Divide and conquer by splitting box types and merging results

B. Greedy algorithm sorting box types by units per box in descending order and picking boxes until the truck is full

C. Breadth-first search exploring all possible box selections up to truck capacity

D. Dynamic programming considering all combinations of boxes and capacities

Solution

1. Step 1: Understand problem constraints

   The problem requires maximizing units loaded on a truck with limited capacity by selecting boxes with different units per box.

2. Step 2: Identify optimal approach

   Since the problem involves discrete box counts and a capacity constraint, the greedy approach does not always guarantee an optimal solution. Dynamic programming considering all combinations ensures the optimal solution by exploring all feasible selections.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP guarantees optimality for knapsack-like problems with discrete items [OK]

Hint: Use DP for discrete knapsack problems to guarantee optimality [OK]

Common Mistakes:

• Assuming greedy always works
• Trying BFS which is inefficient
• Ignoring capacity constraints

3. Given the following code and input arrays, what is the final output printed?

def minDominoRotations(A, B):
    def check(x):
        rotations_a = rotations_b = 0
        for i in range(len(A)):
            if A[i] != x and B[i] != x:
                return -1
            elif A[i] != x:
                rotations_a += 1
            elif B[i] != x:
                rotations_b += 1
        return min(rotations_a, rotations_b)

    rotations = check(A[0])
    if rotations != -1:
        return rotations
    else:
        return check(B[0])

A = [3,5,1,2]
B = [3,6,3,3]
print(minDominoRotations(A, B))

easy

A. -1

B. 2

C. 1

D. 3

Solution

1. Step 1: Check candidate x = A[0] = 3

   i=0: A[0]=3 matches x=3, no rotation.
   i=1: A[1]=5 != 3, B[1]=6 != 3 -> return -1 immediately.

2. Step 2: Check candidate x = B[0] = 3

   i=0: A[0]=3 matches x=3, no rotation.
   i=1: A[1]=5 != 3, B[1]=6 != 3 -> return -1 immediately.
   Both candidates fail, so output is -1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Both candidates fail at i=1, so no solution [OK]

Hint: Check both candidates carefully for early failure [OK]

Common Mistakes:

• Assuming first candidate always works
• Miscounting rotations when both sides match

4. The following code attempts to implement the peak-valley approach but contains a subtle bug. Identify the line causing incorrect profit calculation.

def maxProfit(prices):
    i = 0
    profit = 0
    n = len(prices)
    while i < n - 1:
        while i < n - 1 and prices[i] > prices[i + 1]:
            i += 1
        valley = prices[i]
        while i < n - 1 and prices[i] < prices[i + 1]:
            i += 1
        peak = prices[i]
        profit += peak - valley
    return profit

medium

A. Line with 'while i < n - 1 and prices[i] < prices[i + 1]:'

B. Line with 'valley = prices[i]'

C. Line with 'while i < n - 1 and prices[i] > prices[i + 1]:'

D. Line with 'profit += peak - valley'

Solution

1. Step 1: Compare with correct condition

   The correct condition should be prices[i] >= prices[i + 1] to skip equal or descending prices.

2. Step 2: Identify bug impact

   Using strict '>' misses equal prices, causing incorrect valley selection and possibly negative profit.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Changing '>' to '>=' fixes edge cases with flat prices [OK]

Hint: Check comparison operators in loops for off-by-one errors [OK]

Common Mistakes:

• Using strict inequalities causing missed equal prices
• Adding negative differences to profit
• Off-by-one errors causing index out of range

5. The following code attempts to compute the minimum cost to connect sticks using a min-heap. Identify the bug that causes incorrect results or infinite loops.

medium

A. Line 3: Incorrect base case check for single stick

B. Line 9: Adding cost before popping sticks

C. Line 6: Not heapifying the sticks before processing

D. Line 11: Not pushing the merged stick back into the heap

Solution

1. Step 1: Review the merge loop

   The loop pops two smallest sticks and sums their lengths as cost.

2. Step 2: Check if merged stick is reinserted

   The merged stick must be pushed back into the heap to continue merging. Missing this causes infinite loop or incorrect cost.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Without pushing merged stick, heap shrinks incorrectly -> infinite loop or wrong result [OK]

Hint: Merged sticks must be pushed back to heap [OK]

Common Mistakes:

• Forgetting to push merged stick back
• Incorrect base case handling
• Misordering heap operations