Minimum Number of Platforms in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Minimum Number of Platforms problem?

To find the least number of train platforms required at a station so that no train has to wait for another to leave.

intermediate

Which data structures are commonly used to solve the Minimum Number of Platforms problem efficiently?

Two sorted arrays (one for arrival times and one for departure times) and pointers to traverse them.

intermediate

Explain the two-pointer technique used in the Minimum Number of Platforms problem.

Use one pointer to track arrivals and another for departures. Increment platform count when a train arrives before the earliest departure, else decrement when a train departs.

beginner

Why do we sort arrival and departure times separately in the Minimum Number of Platforms problem?

Sorting helps to process events in chronological order, making it easier to count overlapping trains and platforms needed.

beginner

What does the maximum value of platforms needed during the traversal represent?

It represents the minimum number of platforms required so that no train waits.

What is the first step in solving the Minimum Number of Platforms problem?

A Calculate total travel time

B Count total trains

C Assign platforms randomly

D Sort arrival and departure times separately

Sorting arrival and departure times separately allows us to process events in order.

When do we increase the platform count during traversal?

A When a train arrives before the earliest departure

B When no trains are at the station

C When trains arrive and depart at the same time

D When a train departs before the next arrival

We increase platform count when a train arrives before the earliest train departs, indicating overlap.

What does decrementing the platform count signify in the algorithm?

A A train has departed

B A train has arrived

C A platform is broken

D A train is delayed

Decrementing means a train has left, freeing a platform.

What is the time complexity of the efficient solution for Minimum Number of Platforms?

A O(n^2)

B O(n)

C O(n log n)

D O(log n)

Sorting takes O(n log n), and traversal is O(n), so overall O(n log n).

If arrival times are [9:00, 9:40, 9:50] and departure times are [9:10, 12:00, 11:20], what is the minimum number of platforms needed?

A 1

B 2

C 3

D 4

At 9:50, two trains overlap, so 2 platforms are needed.

Describe the step-by-step approach to find the minimum number of platforms needed for trains arriving and departing at different times.

Think about how to count overlapping trains using sorted times.

Explain why sorting arrival and departure times separately is crucial in solving the Minimum Number of Platforms problem.

Consider how events happen over time at the station.