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

Recall & Review

beginner

What is the problem statement of the Minimum Number of Platforms?

Given arrival and departure times of trains, find the minimum number of platforms required so that no train waits.

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 track how many trains are at the station at the same time.

beginner

What does the variable 'platforms_needed' represent during the algorithm?

'platforms_needed' tracks the current number of trains at the station, indicating how many platforms are occupied at that moment.

beginner

How do we update the count of platforms when a train arrives or departs?

When a train arrives, increment 'platforms_needed'. When a train departs, decrement 'platforms_needed'.

beginner

What is the final answer in the Minimum Number of Platforms problem?

The maximum value of 'platforms_needed' during the process is the minimum number of platforms required.

Why do we need to sort arrival and departure times separately?

A To find the longest train

B To group trains by their platform

C To process events in chronological order

D To count total trains

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

What does an increase in 'platforms_needed' signify?

A A train has departed

B No change

C A platform is freed

D A train has arrived

When a train arrives, 'platforms_needed' increases because one more platform is occupied.

If arrival[i] > departure[j], what should we do in the algorithm?

A Increment platforms_needed

B Decrement platforms_needed

C Do nothing

D Reset platforms_needed

If a train departs before the next arrives, we free a platform by decrementing 'platforms_needed'.

What is the time complexity of the Minimum Number of Platforms algorithm after sorting?

A O(n log n)

B O(n^2)

C O(n)

D O(log n)

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

What does the maximum value of 'platforms_needed' represent?

A Minimum platforms required

B Total trains

C Maximum waiting time

D Number of trains departed

The maximum 'platforms_needed' is the minimum number of platforms needed to avoid waiting.

Explain the step-by-step approach to find the minimum number of platforms needed for trains.

Think about processing train events in order of time.

Why is sorting both arrival and departure times separately important in this problem?

Consider how to know when a platform frees up before next train arrives.