Minimum Number of Platforms in DSA C++

Mental Model

We want to find the smallest number of train platforms needed so that no train has to wait. We do this by checking how many trains overlap in time.

Analogy: Imagine a parking lot where cars arrive and leave at different times. The minimum number of parking spots needed is the maximum number of cars parked at the same time.

Arrivals:  [1:00] -> [1:10] -> [1:20] -> [1:30]
Departures:[1:05] -> [1:15] -> [1:25] -> [1:40]
Platforms needed depends on overlapping times.

Dry Run Walkthrough

Input: arrivals: [900, 940, 950, 1100, 1500, 1800], departures: [910, 1200, 1120, 1130, 1900, 2000]

Goal: Find the minimum number of platforms needed so that no train waits.

Step 1: Sort arrivals and departures separately

arrivals: [900, 940, 950, 1100, 1500, 1800]
departures: [910, 1120, 1130, 1200, 1900, 2000]

Why: Sorting helps us compare arrival and departure times in order.

Step 2: Compare first arrival (900) with first departure (910), arrival < departure, increase platform count to 1

platforms = 1, max_platforms = 1
arr_idx=1, dep_idx=0

Why: Train arrives before the first train leaves, so we need a platform.

Step 3: Compare arrival 940 with departure 910, arrival > departure, decrease platform count to 0, move departure index

platforms = 0, max_platforms = 1
arr_idx=1, dep_idx=1

Why: One train left before next arrived, freeing a platform.

Step 4: Compare arrival 940 with departure 1120, arrival < departure, increase platform count to 1

platforms = 1, max_platforms = 1
arr_idx=2, dep_idx=1

Why: New train arrives before previous train leaves, need platform.

Step 5: Compare arrival 950 with departure 1120, arrival < departure, increase platform count to 2, update max_platforms to 2

platforms = 2, max_platforms = 2
arr_idx=3, dep_idx=1

Why: Two trains overlap, need two platforms.

Step 6: Compare arrival 1100 with departure 1120, arrival < departure, increase platform count to 3, update max_platforms to 3

platforms = 3, max_platforms = 3
arr_idx=4, dep_idx=1

Why: Three trains overlap, need three platforms.

Step 7: Compare arrival 1500 with departure 1120, arrival > departure, decrease platform count to 2, move departure index

platforms = 2, max_platforms = 3
arr_idx=4, dep_idx=2

Why: One train left, freeing a platform.

Step 8: Compare arrival 1500 with departure 1130, arrival > departure, decrease platform count to 1, move departure index

platforms = 1, max_platforms = 3
arr_idx=4, dep_idx=3

Why: Another train left, freeing a platform.

Step 9: Compare arrival 1500 with departure 1200, arrival > departure, decrease platform count to 0, move departure index

platforms = 0, max_platforms = 3
arr_idx=4, dep_idx=4

Why: Another train left, freeing a platform.

Step 10: Compare arrival 1500 with departure 1900, arrival < departure, increase platform count to 1

platforms = 1, max_platforms = 3
arr_idx=5, dep_idx=4

Why: New train arrives before previous train leaves, need platform.

Step 11: Compare arrival 1800 with departure 1900, arrival < departure, increase platform count to 2

platforms = 2, max_platforms = 3
arr_idx=6, dep_idx=4

Why: Two trains overlap, need two platforms.

Result:

Final max_platforms = 3
Answer: Minimum 3 platforms needed

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int findMinPlatforms(vector<int> arrivals, vector<int> departures) {
    sort(arrivals.begin(), arrivals.end());
    sort(departures.begin(), departures.end());

    int platform_needed = 0, max_platforms = 0;
    int i = 0, j = 0;
    int n = arrivals.size();

    while (i < n && j < n) {
        if (arrivals[i] <= departures[j]) {
            platform_needed++;
            if (platform_needed > max_platforms) {
                max_platforms = platform_needed;
            }
            i++;
        } else {
            platform_needed--;
            j++;
        }
    }
    return max_platforms;
}

int main() {
    vector<int> arrivals = {900, 940, 950, 1100, 1500, 1800};
    vector<int> departures = {910, 1200, 1120, 1130, 1900, 2000};

    int result = findMinPlatforms(arrivals, departures);
    cout << "Minimum number of platforms needed: " << result << endl;
    return 0;
}

sort(arrivals.begin(), arrivals.end()); sort(departures.begin(), departures.end());

Sort arrival and departure times to compare in order.

while (i < n && j < n) {

Traverse both arrays to check overlapping trains.

if (arrivals[i] <= departures[j]) {

If next train arrives before or at the same time as a train departs, increase platform count.

platform_needed++;

Add one platform for the arriving train.

if (platform_needed > max_platforms) { max_platforms = platform_needed; }

Update max platforms if current needed is higher.

i++;

Move to next arrival.

} else { platform_needed--; j++; }

If train departs before next arrival, free a platform and move departure pointer.

Output

Minimum number of platforms needed: 3

Complexity Analysis

Time: O(n log n) because we sort the arrival and departure arrays, then traverse them once.

Space: O(1) because we use only a few extra variables, sorting done in place.

vs Alternative: Naive approach checks every train against every other train, O(n^2), which is slower than sorting and linear traversal.

Edge Cases

No trains (empty arrays)

Returns 0 platforms needed.

DSA C++

while (i < n && j < n) {

All trains arrive and depart at the same time

Platforms needed equals number of trains.

DSA C++

if (arrivals[i] <= departures[j]) {

Trains arrive after all others depart (no overlap)

Only 1 platform needed.

DSA C++

else { platform_needed--; j++; }

When to Use This Pattern

When you see a problem asking for minimum resources to handle overlapping intervals, reach for the 'Minimum Number of Platforms' pattern because sorting and two-pointer traversal efficiently finds maximum overlap.

Common Mistakes

Mistake: Not sorting arrival and departure times separately before processing.
Fix: Always sort both arrays independently to correctly compare times in order.

Mistake: Using < instead of <= in comparison, causing incorrect platform count when arrival equals departure.
Fix: Use less than or equal (<=) to count arrival before or at departure correctly.

Summary

Finds the minimum number of platforms needed so no train waits by counting overlapping trains.

Use when scheduling resources for intervals that may overlap in time.

Sort arrivals and departures separately, then use two pointers to track overlaps and find max platforms needed.

Practice

1. What does the "Minimum Number of Platforms" problem primarily ask you to find?

easy

A. The total number of trains passing through the station

B. The maximum number of trains arriving at the station

C. The least number of train platforms needed so no train waits

D. The shortest time a train stays on a platform

Solution

1. Step 1: Understand the problem goal

   The problem asks for the minimum platforms so that no train waits due to platform unavailability.

2. Step 2: Clarify what is being counted

   We count platforms needed to handle overlapping train schedules without delay.

3. Final Answer:

   The least number of train platforms needed so no train waits -> Option C

4. Quick Check:

   Minimum platforms = no waiting trains [OK]

Hint: Focus on overlapping train times to find platform count [OK]

Common Mistakes:

• Confusing total trains with platforms needed
• Ignoring overlapping arrival and departure times
• Thinking about train speed or distance

2. Which of the following C++ code snippets correctly declares vectors to store arrival and departure times for the Minimum Number of Platforms problem?

easy

A. vector<int> arrival; vector<int> departure;

B. vector arrival, departure int;

C. std::vector arrival(int), departure(int);

D. std::vector<int> arrival, departure;

Solution

1. Step 1: Check correct vector syntax in C++

   Vectors must be declared with type inside angle brackets and variable names, e.g., vector<int> arrival;

2. Step 2: Identify valid declarations

   vector<int> arrival; vector<int> departure; uses correct syntax for two separate vectors: vector<int> arrival; vector<int> departure;

3. Final Answer:

   vector<int> arrival; vector<int> departure; -> Option A

4. Quick Check:

   Correct vector syntax = vector<int> arrival; vector<int> departure; [OK]

Hint: Use vector<int> name; for integer vectors in C++ [OK]

Common Mistakes:

• Missing angle brackets <> for vector type
• Incorrect order of type and variable name
• Using wrong syntax like vector arrival(int)

3. Consider the following C++ code snippet for Minimum Number of Platforms problem:

std::vector<int> arrival = {900, 940, 950, 1100, 1500, 1800};
std::vector<int> departure = {910, 1200, 1120, 1130, 1900, 2000};

int platforms = 1, result = 1;
int i = 1, j = 0;

while (i < arrival.size() && j < departure.size()) {
  if (arrival[i] <= departure[j]) {
    platforms++;
    i++;
  } else {
    platforms--;
    j++;
  }
  if (platforms > result) result = platforms;
}

std::cout << result << std::endl;

What is the output of this code?

medium

A. 2

B. 3

C. 4

D. 1

Solution

1. Step 1: Trace arrival and departure comparisons

   Compare arrival[i] and departure[j]: - i=1(940) <= j=0(910)? No, so platforms-- (1->0), j=1 - i=1(940) <= j=1(1200)? Yes, platforms++ (0->1), i=2 - i=2(950) <= j=1(1200)? Yes, platforms++ (1->2), i=3 - i=3(1100) <= j=1(1200)? Yes, platforms++ (2->3), i=4 - i=4(1500) <= j=1(1200)? No, platforms-- (3->2), j=2 - i=4(1500) <= j=2(1120)? No, platforms-- (2->1), j=3 - i=4(1500) <= j=3(1130)? No, platforms-- (1->0), j=4 - i=4(1500) <= j=4(1900)? Yes, platforms++ (0->1), i=5 - i=5(1800) <= j=4(1900)? Yes, platforms++ (1->2), i=6 (end)

2. Step 2: Find maximum platforms during process

   Maximum platforms reached is 3 during the steps.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Max overlapping trains = 3 [OK]

Hint: Count overlaps by comparing sorted arrivals and departures [OK]

Common Mistakes:

• Not updating platform count correctly
• Mixing up arrival and departure indices
• Assuming max platforms equals total trains

4. The following code snippet is intended to find the minimum number of platforms needed. Identify the bug:

std::vector<int> arrival = {900, 940, 950, 1100};
std::vector<int> departure = {910, 1120, 1130, 1200};

int platforms = 1, result = 1;
int i = 1, j = 0;

while (i < arrival.size() && j < departure.size()) {
  if (arrival[i] < departure[j]) {
    platforms++;
    i++;
  } else {
    platforms--;
    j++;
  }
  if (platforms > result) result = platforms;
}

std::cout << result << std::endl;

medium

A. The comparison should be <= instead of < in if condition

B. The initial value of platforms should be 0, not 1

C. The vectors arrival and departure are not sorted

D. The loop condition should use || instead of &&

Solution

1. Step 1: Analyze the if condition for arrival and departure

   The condition uses arrival[i] < departure[j], but trains arriving exactly when another departs need a platform, so <= is correct.

2. Step 2: Understand impact of using < instead of <=

   Using < misses cases where arrival equals departure, causing undercount of platforms needed.

3. Final Answer:

   The comparison should be <= instead of < in if condition -> Option A

4. Quick Check:

   Use <= to count overlapping trains correctly [OK]

Hint: Use <= to include trains arriving exactly at departure time [OK]

Common Mistakes:

• Using < instead of <= causes wrong platform count
• Not sorting arrival and departure arrays
• Incorrect loop condition with && vs ||

5. You have the following train schedules:

Arrival: {1000, 1010, 1025, 1030, 1040}
Departure: {1015, 1020, 1035, 1045, 1050}

What is the minimum number of platforms required so that no train waits? Choose the correct approach and answer.

hard

A. Sort only arrival times and count unique values; answer is 4

B. Count total trains; answer is 5

C. Use a hash map to count trains per time; answer is 2

D. Sort both arrays, then use two pointers to count overlaps; answer is 2

Solution

1. Step 1: Sort arrival and departure times

   Both arrays are already sorted: arrival = {1000,1010,1025,1030,1040}, departure = {1015,1020,1035,1045,1050}

2. Step 2: Use two pointers to count overlapping trains

   Compare arrival[i] and departure[j]: - 1010 <= 1015: platforms=2 - 1025 <= 1015? No, platforms=1 - 1025 <= 1020? No, platforms=0 - 1025 <= 1035? Yes, platforms=1 - 1030 <= 1035? Yes, platforms=2 - 1040 <= 1035? No, platforms=1 - 1040 <= 1045? Yes, platforms=2 Maximum platforms needed = 2 during overlaps.

3. Final Answer:

   Sort both arrays, then use two pointers to count overlaps; answer is 2 -> Option D

4. Quick Check:

   Two pointer overlap count = 2 platforms [OK]

Hint: Sort arrivals and departures, count overlaps with two pointers [OK]

Common Mistakes:

• Counting total trains instead of overlaps
• Not sorting both arrays
• Using incorrect data structures like hash maps unnecessarily