Minimum Number of Platforms in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the minimum number of platforms needed?

Given arrival and departure times of trains, what is the minimum number of platforms required so that no train waits?

DSA C++

int findPlatform(int arr[], int dep[], int n) {
    sort(arr, arr + n);
    sort(dep, dep + n);
    int platform_needed = 1, result = 1;
    int i = 1, j = 0;
    while (i < n && j < n) {
        if (arr[i] <= dep[j]) {
            platform_needed++;
            i++;
            if (platform_needed > result)
                result = platform_needed;
        } else {
            platform_needed--;
            j++;
        }
    }
    return result;
}

// Example usage:
// arr = {900, 940, 950, 1100, 1500, 1800}
// dep = {910, 1200, 1120, 1130, 1900, 2000}
// n = 6
// Output: 3

A 3

B 5

C 2

D 4

💡 Hint

Sort arrival and departure times separately and compare them to find overlaps.

The code sorts arrival and departure times. It then uses two pointers to count how many trains are at the station at the same time. The maximum count is the minimum number of platforms needed.

❓ Predict Output

intermediate

Output of platform calculation with overlapping trains

What is the output of the following code snippet for given train times?

DSA C++

int arr[] = {1000, 1010, 1025, 1030};
int dep[] = {1020, 1035, 1040, 1050};
int n = 4;
int result = findPlatform(arr, dep, n);
std::cout << result << std::endl;

A 4

B 2

C 3

D 1

💡 Hint

Count how many trains overlap at the same time.

Trains overlap between 1010 and 1020 (2 trains), and between 1025 and 1035 (3 trains). Maximum overlap is 3, so output is 3.

🧠 Conceptual

advanced

Why sorting arrival and departure times separately works?

Why do we sort arrival and departure times separately when calculating minimum platforms?

A Because sorting together would mix arrival and departure times causing incorrect counts.

B Because it allows us to process events in chronological order to count overlaps correctly.

C Because sorting separately reduces the time complexity from O(n^2) to O(n log n).

D Because it helps to find the maximum gap between trains.

💡 Hint

Think about how to track when trains arrive and leave in order.

Sorting arrival and departure times separately lets us move through events in order, increasing platform count on arrival and decreasing on departure, accurately tracking overlaps.

🔧 Debug

advanced

Identify the bug in platform calculation code

What is the error in this code snippet for finding minimum platforms? int findPlatform(int arr[], int dep[], int n) { sort(arr, arr + n); sort(dep, dep + n); int platform_needed = 0, result = 0; int i = 0, j = 0; while (i < n && j < n) { if (arr[i] < dep[j]) { platform_needed++; i++; if (platform_needed > result) result = platform_needed; } else { platform_needed--; j++; } } return result; }

A The comparison should be arr[i] <= dep[j] to count trains arriving exactly when another departs.

B The initial platform_needed should be 1, not 0.

C The loop should run while i < n only, not j < n.

D The result should be updated before incrementing platform_needed.

💡 Hint

Consider trains arriving exactly when another departs.

If arrival time equals departure time, the platform is still needed. Using < instead of <= misses this case, causing wrong platform count.

🚀 Application

expert

Calculate minimum platforms for large input efficiently

You have 10^6 trains with arrival and departure times. Which approach is best to find minimum platforms efficiently?

A Use a hash map to store counts of trains at each time and find max count in O(n) time.

B Use nested loops to compare each train with every other train to count overlaps in O(n^2) time.

C Sort trains by arrival time only and count platforms by checking previous trains' departure times.

D Sort arrival and departure arrays separately and use two pointers to count overlaps in O(n log n) time.

💡 Hint

Think about time complexity and scalability for large inputs.

Sorting arrival and departure times separately and using two pointers is efficient and scalable for large inputs, running in O(n log n) time.

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