Minimum Number of Platforms in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Minimum Platforms Calculation

What is the output of the following Java code that calculates the minimum number of platforms needed for trains?

DSA Java

import java.util.*;
public class Main {
    public static int findPlatform(int[] arr, int[] dep) {
        Arrays.sort(arr);
        Arrays.sort(dep);
        int platform_needed = 1, result = 1;
        int i = 1, j = 0;
        while (i < arr.length && j < dep.length) {
            if (arr[i] <= dep[j]) {
                platform_needed++;
                i++;
            } else {
                platform_needed--;
                j++;
            }
            if (platform_needed > result) result = platform_needed;
        }
        return result;
    }
    public static void main(String[] args) {
        int[] arr = {900, 940, 950, 1100, 1500, 1800};
        int[] dep = {910, 1200, 1120, 1130, 1900, 2000};
        System.out.println(findPlatform(arr, dep));
    }
}

A 3

B 4

C 2

D 5

💡 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 simultaneously. The maximum count is the minimum number of platforms needed.

For the given times, the maximum overlap is 3 trains.

🧠 Conceptual

intermediate

Understanding the Core Logic

Which of the following best describes the core logic used to find the minimum number of platforms needed for trains?

A Calculate the difference between the earliest arrival and latest departure times.

B Sort trains by arrival time only and count trains arriving before the last departure.

C Sort arrival and departure times separately, then use two pointers to count overlapping trains.

D Use a hash map to count trains arriving at each time and find the maximum count.

💡 Hint

Think about how sorting helps in comparing arrival and departure times.

The correct approach sorts both arrival and departure times and uses two pointers to track how many trains are at the station at the same time.

🔧 Debug

advanced

Identify the Bug in Platform Calculation

What error will occur if the condition in the while loop is changed from 'arr[i] <= dep[j]' to 'arr[i] < dep[j]' in the platform calculation code?

DSA Java

while (i < arr.length && j < dep.length) {
    if (arr[i] < dep[j]) {
        platform_needed++;
        i++;
    } else {
        platform_needed--;
        j++;
    }
    if (platform_needed > result) result = platform_needed;
}

A No error; the output remains the same as original.

B The code will throw an ArrayIndexOutOfBoundsException.

C The code will overestimate the number of platforms needed for all cases.

D The code will underestimate the number of platforms needed when arrival and departure times are equal.

💡 Hint

Consider what happens when a train arrives exactly when another departs.

Changing '<=' to '<' causes the code to treat trains arriving exactly at departure time as needing a new platform, which underestimates platforms needed.

❓ Predict Output

advanced

Output with Overlapping Trains

What is the output of the following code snippet for minimum platforms?

DSA Java

int[] arr = {1000, 1010, 1025, 1030};
int[] dep = {1015, 1020, 1035, 1040};
System.out.println(findPlatform(arr, dep));

// findPlatform method same as in c1

A 3

B 2

C 4

D 1

💡 Hint

Check how many trains overlap at the same time.

The maximum overlap is 3 trains between 1025 and 1030.

🚀 Application

expert

Minimum Platforms for Large Input

Given 1 million trains with random arrival and departure times, which approach is most efficient to find the minimum number of platforms needed?

A Use nested loops to compare each train with every other train, resulting in O(n^2) time.

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

C Use a hash map to count trains at each time point, which requires O(n * max_time) time.

D Sort trains by arrival time only and count overlaps using a queue in O(n) time.

💡 Hint

Consider time complexity and scalability for large inputs.

Sorting both arrays 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 ask you to find given train arrival and departure times?

easy

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

B. The total number of trains arriving in a day

C. The longest time a train stays on a platform

D. The earliest train arrival time

Solution

1. Step 1: Understand the problem goal

   The problem asks for the minimum number of platforms required so that no train has to wait for another to leave.

2. Step 2: Clarify what is being counted

   We count how many trains overlap in time on the station to find the minimum platforms needed.

3. Final Answer:

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

4. Quick Check:

   Minimum platforms = max trains overlapping [OK]

Hint: Count overlapping trains to find minimum platforms needed [OK]

Common Mistakes:

• Confusing total trains with platforms needed
• Ignoring overlapping times
• Counting earliest arrival only

2. Which Java data structure is best suited to efficiently find the minimum number of platforms needed given sorted arrival and departure arrays?

easy

A. PriorityQueue (Min-Heap)

B. Stack

C. LinkedList

D. HashMap

Solution

1. Step 1: Identify the need for quick minimum departure tracking

   We need to know the earliest train departure to free a platform, so a min-heap helps track minimum departure time efficiently.

2. Step 2: Match data structure to problem

   PriorityQueue in Java is a min-heap, perfect for this use case to manage platforms dynamically.

3. Final Answer:

   PriorityQueue (Min-Heap) -> Option A

4. Quick Check:

   Min-heap tracks earliest departure [OK]

Hint: Use min-heap to track earliest departure times [OK]

Common Mistakes:

• Using HashMap which doesn't maintain order
• Using Stack which is LIFO, not suitable
• Using LinkedList which is inefficient for min queries

3. What is the output of the following Java code snippet that calculates minimum platforms?

int[] arrivals = {900, 940, 950, 1100, 1500, 1800};
int[] departures = {910, 1200, 1120, 1130, 1900, 2000};
System.out.println(minPlatforms(arrivals, departures));

// Assume minPlatforms returns the minimum platforms needed

medium

A. 2

B. 4

C. 3

D. 5

Solution

1. Step 1: Sort arrival and departure times

   Arrivals: 900, 940, 950, 1100, 1500, 1800 Departures: 910, 1120, 1130, 1200, 1900, 2000

2. Step 2: Count overlapping trains

   At 900-910: 1 train At 940-1120: 2 trains overlap At 950-1130: 3 trains overlap (max) After 1130, trains start leaving, so max platforms needed = 3

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Max overlap = 3 platforms [OK]

Hint: Find max overlapping intervals after sorting [OK]

Common Mistakes:

• Not sorting times before processing
• Counting total trains instead of overlaps
• Mixing arrival and departure arrays

4. Identify the bug in this Java method to find minimum platforms:

public static int minPlatforms(int[] arr, int[] dep) {
    Arrays.sort(arr);
    Arrays.sort(dep);
    int i = 0, j = 0, platforms = 0, maxPlatforms = 0;
    while (i < arr.length && j < dep.length) {
        if (arr[i] <= dep[j]) {
            platforms++;
            i++;
        } else {
            platforms--;
            j++;
        }
        maxPlatforms = Math.max(maxPlatforms, platforms);
    }
    return maxPlatforms;
}

medium

A. The loop should run while i < arr.length only

B. The condition should be arr[i] < dep[j] instead of <= to avoid counting simultaneous arrival and departure

C. The platforms variable should not be decremented

D. Arrays.sort should be called only on arrivals

Solution

1. Step 1: Analyze the comparison condition

   The condition arr[i] <= dep[j] counts a train arriving exactly when another departs as overlapping, increasing platforms unnecessarily.

2. Step 2: Correct the condition to avoid overcounting

   Changing to arr[i] < dep[j] treats simultaneous arrival and departure as no overlap, which is correct for platform counting.

3. Final Answer:

   The condition should be arr[i] < dep[j] instead of <= to avoid counting simultaneous arrival and departure -> Option B

4. Quick Check:

   Use strict less than for arrival vs departure [OK]

Hint: Use < not <= to avoid counting simultaneous arrival and departure [OK]

Common Mistakes:

• Using <= causes overcounting platforms
• Not sorting both arrays
• Incorrect loop condition

5. Given arrival times [1000, 1010, 1025, 1030, 1040] and departure times [1020, 1035, 1045, 1050, 1100], what is the minimum number of platforms needed if trains arriving exactly when another departs do NOT require a new platform?

hard

A. 4

B. 5

C. 2

D. 3

Solution

1. Step 1: Sort and analyze arrival and departure times

   Arrivals: 1000, 1010, 1025, 1030, 1040 Departures: 1020, 1035, 1045, 1050, 1100

2. Step 2: Count overlapping trains considering no extra platform if arrival equals departure

   1000-1020: 1 train 1010-1035: overlaps with first, total 2 1025-1045: first gone at 1020, overlaps with second, total 2 1030-1050: overlaps with second (till 1035) and third (till 1045), total 3 1040-1100: second gone at 1035, overlaps with third, fourth, total 3 (max)

3. Step 3: Adjust for arrival equals departure rule

   No arrivals equal departures here, so max platforms = 3

4. Final Answer:

   3 -> Option D

5. Quick Check:

   Max overlap = 3 platforms [OK]

Hint: Count overlaps, exclude equal arrival and departure as overlap [OK]

Common Mistakes:

• Counting equal arrival and departure as overlap
• Not sorting times
• Miscounting overlaps